#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int CURR=0;
int same(int x){
int temp=Query(x);
int res=CURR==temp;
CURR=temp;
return res;
}
int n;
int in[50005];
int mask[50005];
vector<ii> v;
int pos[70005];
vector<int> posi[70005];
vector<int> posi2[70005];
int done[70005];
void solve(vector<int> l,vector<int> r,int TOGGLE){
int n=sz(l);
v.clear();
rep(x,0,70005) posi[x].clear();
rep(x,0,70005) posi2[x].clear();
memset(done,-1,sizeof(done));
rep(x,0,n) in[x]=TOGGLE;
rep(x,0,n) mask[x]=0;
//for (auto it:l) cout<<it<<" "; cout<<endl;
//for (auto it:r) cout<<it<<" "; cout<<endl;
//cout<<TOGGLE<<endl<<endl;
int s=0;
while ((1<<s)<n) s++;
rep(x,0,1<<s){
int curr=0;
int num=0;
rep(bit,0,s){
int temp=!!(x&(1<<bit));
if (curr!=temp) num++;
curr=temp;
}
v.pub({num,x});
}
sort(all(v));
if (TOGGLE==1) for (auto &it:v) it.se^=(1<<s)-1;
rep(x,0,sz(v)) pos[v[x].se]=x;
int af=(1<<(s-1))-1;
rep(x,0,n) posi[v[x].se&af].pub(v[x].se);
rep(x,0,n) posi2[v[x].se&(af>>1)].pub(v[x].se);
rep(bit,0,s){
rep(x,0,n){
int val=!!(v[x].se&(1<<bit));
if (in[x]!=val) same(l[x]);
in[x]=val;
}
rep(x,0,n){
if (bit==s-1){
if (sz(posi[mask[x]])==1){
mask[x]=posi[mask[x]][0];
}
else if (done[mask[x]]==-1){
if (same(r[x])){
done[mask[x]]=0;
mask[x]|=1<<bit;
}
else{
done[mask[x]]=1;
}
}
else{
mask[x]|=done[mask[x]]<<bit;
}
}
else{
if (same(r[x])) mask[x]|=1<<bit;
}
}
}
rep(x,0,n) Answer(l[pos[mask[x]]],r[x]);
}
void Solve(signed N) {
n=N;
vector<int> idx;
rep(x,1,2*n+1) idx.pub(x);
shuffle(all(idx),rng);
vector<int> l1,r1;
vector<int> l2,r2;
vector<int> l3,r3;
rep(x,0,n){
if (same(idx[x])) r1.pub(idx[x]);
else l1.pub(idx[x]);
}
vector<int> temp;
for (auto it:l1){
if (same(it)) temp.pub(it);
else l2.pub(it);
}
solve(r1,temp,1);
rep(x,n,2*n){
if (same(idx[x])) r3.pub(idx[x]);
else l3.pub(idx[x]);
}
temp.clear();
for (auto it:l3){
if (same(it)) temp.pub(it);
else r2.pub(it);
}
solve(r3,temp,1);
solve(l2,r2,0);
}
