#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int curr = 0;
bool change(int u){
int nxt = Query(u);
bool res = (nxt != curr);
curr = nxt;
return res;
}
void rec(vector<int> &A,vector<int> &B,bool rev){
int len = A.size();
if(len == 1){
Answer(A[0],B[0]);
return;
}
shuffle(A.begin(),A.end(),rng);
shuffle(B.begin(),B.end(),rng);
int mid = (rev?382:618)*len/1000;
if(mid == 0) mid++;
if(mid == len) mid--;
vector<int> nA[2],nB[2];
for(int i=0;i<len;i++){
if(i < mid){
change(A[i]);
nA[0].push_back(A[i]);
}else nA[1].push_back(A[i]);
}
for(int i=0;i<len;i++){
if(nB[0].size() == nA[0].size()) nB[1].push_back(B[i]);
else if(nB[1].size() == nA[1].size()) nB[0].push_back(B[i]);
else if(change(B[i])) nB[rev^1].push_back(B[i]);
else nB[rev].push_back(B[i]);
}
rec(nA[0],nB[0],rev^1);
rec(nA[1],nB[1],rev);
}
void Solve(int N){
vector<int> group[2];
for(int i=1;i<=2*N;i++) group[change(i)].push_back(i);
rec(group[0],group[1],1);
}
