#include "Memory2_lib.h" //subtask 12 but K = 300
#include <bits/stdc++.h>
using namespace std;
namespace{
}
void Solve(int T, int N){
if(N == 1){
Answer(0, 1, 1);
return;
}
if(N == 2){
for(int i = 0; i < 4; ++i){
for(int j = i+1; j < 4; ++j){
if(Flip(i, j) == 1){
Answer(i, j, 1);
int x = -1, y = -1;
for(int k = 0; k < 4; ++k){
if(k != i && k != j){
if(x == -1) x = k;
else y = k;
}
}
Answer(x, y, 0);
return;
}
}
}
assert(false);
return;
}
int a = 0, b = 1, c = -1;
int cur = Flip(0, 1);
vector<pair<int, int>> assertions;
vector<int> answer(2 * N, -1);
for(int i = 2; i < 2 * N; ++i){
int ai = Flip(a, i);
int bi = Flip(b, i);
int ci = (c != -1 ? Flip(c, i) : -1);
int nw = max({ai, bi, ci});
if(cur < nw){
if(nw == ai) {
assertions.emplace_back(b, cur);
b = i;
}
else if(nw == bi) {
assertions.emplace_back(a, cur);
a = i;
}
else{
assertions.emplace_back(a, cur);
assertions.emplace_back(b, cur);
a = c;
b = i;
}
cur = nw; c = -1;
} else if(cur == nw) c = i;
else{
assertions.emplace_back(i, nw);
}
}
for(auto [x, y] : assertions) {
answer[x] = y;
}
if(c == -1){
assert(cur == N-1);
answer[a] = N-1;
answer[b] = N-1;
} else{
assert(false);
}
for(int i = 0; i < 2 * N; ++i){
if(answer[i] == -1){
answer[i] = Flip(a, i);
}
}
vector<pair<int, int>> position(N, make_pair(-1, -1));
for(int i = 0; i < 2 * N; ++i){
assert(answer[i] != -1);
if(position[answer[i]].first == -1) position[answer[i]].first = i;
else {
assert(position[answer[i]].second == -1);
position[answer[i]].second = i;
}
}
for(int i = 0; i < N; ++i){
Answer(position[i].first, position[i].second, i);
}
}
//g++ -o grader grader.cpp Memory2.cpp
