#include "minerals.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(6);
vector<int> in, a, b;
int ans=0, budget=0;
int Flip(int x){
in[x]=!in[x];
budget++;
return Query(x);
}
int Set(int x, int v){
if(in[x] == v) {
return ans;
}
else {
return Flip(x);
}
}
void Solve(int N) {
int n = N;
in.resize(2*N+4, 0);
for(int i=1;i<=2*n;i++){
int nv=Set(i, 1);
if(nv == ans + 1){
a.pb(i);
}
else {
b.pb(i);
}
ans = nv;
}
shuffle(b.begin(),b.end(), rng);
/*for(int i=0;i<n;i++){
cout<<a[i]<<endl;
}*/
vector<int> to(2*n+5, 0);
auto dnc=[&](auto && dnc, vector<int> A, vector<int> B)->void{
//cout<<"A is "; for(auto it : A)cout<<it<<" "; cout<<endl;
//cout<<"B is "; for(auto it : B)cout<<it<<" "; cout<<endl;
assert(sz(A) == sz(B));
if(A.empty()) return;
if(sz(B)==1){
to[B[0]]=A[0];
return;
}
vector<int> lA, lB, rA, rB;
int left=0, right=0;
for(int i=0;i<sz(A)/2;i++){
ans=Set(A[i], 1);
lA.pb(A[i]);
left++;
}
for(int i=sz(A)/2;i<sz(A);i++){
ans=Set(A[i], 0);
rA.pb(A[i]);
right++;
}
for(int i=0;i<sz(B);i++){
if(left==0){
rB.pb(B[i]);
}
else if(right == 0){
lB.pb(B[i]);
}
else {
int nv=Flip(B[i]);
if(nv != ans){
rB.pb(B[i]);
right--;
}
else {
lB.pb(B[i]);
left--;
}
ans=nv;
}
}
dnc(dnc, lA, lB);
dnc(dnc, rA, rB);
};
dnc(dnc, a, b);
/*for(int bit=0;bit<16;bit++){
int left=0, right=0;
for(int i=0;i<n;i++){
if(((1<<bit) & i)==0){ // turn on the left half.
left++;
ans=Set(a[i], 1);
}
else {
right++;
ans=Set(a[i], 0);
}
}
for(int i=0;i<n;i++){
if(left == 0){
to[i] += (1<<bit);
right--;
}
else if (right == 0){
left--;
}
else{
int nv=Flip(b[i]);
if(abs(ans-nv) == 1){ // its in the right half.
to[i] += (1<<bit);
right--;
}
else left--;
ans=nv;
}
}
printf("bit %d, budget %d\n",bit,budget);
}*/
for(int i=0;i<n;i++){
Answer(b[i], to[b[i]]);
}
}
