#include <bits/stdc++.h>
#include <limits>
#include "testlib.h"
 
using namespace std;
 
using u32 = uint32_t;
constexpr static u32 HASH_BASE = 653;
constexpr static u32 SECRET_SEED = 02'11'2025;
struct Secret {
    std::mt19937 gen;
    u32 hash;
 
    Secret() : gen(SECRET_SEED), hash(0u) {}
 
    u32 Protect(u32 x) {
        x ^= gen();
        hash = hash * HASH_BASE + x;
        return x;
    }
};

const int N = 30'000;
const int Q = 1'000'000;
const int GROUPS = 4;
const int MAXN[GROUPS + 1] = {100, 100, 100, 1'000, N};
const int MAXQ[GROUPS + 1] = {4950, 4950, 4950, 100'000, Q};
 
int main(int argc, char** argv) {
    registerValidation(argc, argv);

    const int group = validator.group().empty() ? 0 : atoi(validator.group().c_str());
    int t = inf.readInt(1, MAXN[group], "t");
    inf.readSpace();
    int q = inf.readInt(1, MAXQ[group], "q");
    ensuref(q == MAXQ[group], "correct q");
    inf.readEoln();
 
    Secret secret;

    int left = MAXN[group];
 
    for (int testid = 1; testid <= t; ++testid) {
        setTestCase(testid);
        int n = inf.readInt(1, left, "n");
        left -= n;
        ensuref(left >= 0, "sum does not exceed");
        ensuref(n % 2 == 1, "n is odd");
        inf.readEoln();
        auto p = inf.readLongs(n, 0, (1ll << 32) - 1, "p");
        inf.readEoln();

        for (auto& x : p) {
            x = secret.Protect(x);
        }
 
        auto sorted_p = p;
        sort(sorted_p.begin(), sorted_p.end());
        for (int i = 0; i < n; ++i) {
            ensuref(sorted_p[i] == i + 1, "p is not a permutation");
        }

        if (group == 1) {
            for (int i = 1; i <= (n + 1) / 2; ++i) {
                ensuref(p[2 * i - 2] == (n - 1) / 2 + i, "group 1");
            }
        }
    }

    inf.readEof();
}
