#include <bits/stdc++.h>
#include "minerals.h"
#define int LL //__int128
#define double long double
using namespace std;
using LL=long long;
using uLL=unsigned long long;
using pii=pair<LL,LL>;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair
#define MOD (int)(1000000007)
#define INF (int)(1000000000000000ll) //1e15
#define EPS (1e-6)
#ifdef NYAOWO
#include "debug.hpp"
inline void USACO(const string &s) { cerr<<"USACO: "<<s<<"\n"; }
#else
#define debug(...)
inline void timer(){}
inline void USACO(const string &s){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#endif
inline void NYA() { ios::sync_with_stdio(false); cin.tie(0); }
inline int gcd(int a,int b) { return __gcd(a,b); }
inline int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
int ans=1;
while(p){
if(p&1) ans=ans*b%mod;
p/=2; b=b*b%mod;
}
return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
template<typename T> inline void chmin(T &_a,const T &_b) { if(_b<_a) _a=_b; }
template<typename T> inline void chmax(T &_a,const T &_b) { if(_b>_a) _a=_b; }
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Interactor{
bitset<90000> bs;
int last=0;
void init(){
bs.reset();
}
bool push(int x){
bool ans=false;
if(!bs[x]){
int now=Query(x);
bs[x]=true;
ans=(now!=last);
last=now;
}
return ans;
}
bool pop(int x){
bool ans=false;
if(bs[x]){
int now=Query(x);
bs[x]=false;
ans=(now!=last);
last=now;
}
return ans;
}
bool toggle(int x){
int now=Query(x);
bs[x]=!bs[x];
bool ans=(now==last);
last=now;
return ans;
}
}inter;
void solve(vector<int> &vl,vector<int> &vr,int l,int r,bool fill){
//debug(vl,vr,l,r,fill);
if(sz(vl)==1){
Answer(vl[0],vr[l]);
return;
}
int n=max(1ll,sz(vl)/3);
int m=sz(vl)-n;
For(i,l,l+n-1) inter.toggle(vr[i]);
vector<int> vll,vlr;
for(auto &i:vl){
if(sz(vll)==n) vlr.eb(i);
else if(sz(vlr)==m) vll.eb(i);
else{
bool res=inter.toggle(i);
if(fill!=res) vll.eb(i);
else vlr.eb(i);
}
}
solve(vll,vr,l,l+n-1,!fill);
solve(vlr,vr,l+n,r,fill);
}
void Solve(int32_t n){
vector<int> l,r;
For(i,1,n*2){
if(inter.toggle(i)) l.eb(i);
else r.eb(i);
}
random_shuffle(all(r));
solve(l,r,0,n-1,true);
// vector<int> t(n);
// For(pos,0,15){
// For(i,0,n-1){
// if((i&(1<<pos))==0) inter.push(r[i]);
// else inter.pop(r[i]);
// }
// int now=0;
// For(i,0,n-1){
// if(!inter.toggle(l[i])){
// t[now]=l[i];
// now++;
// l[i]=0;
// }
// }
// For(i,0,n-1) if(l[i]!=0){
// t[now]=l[i];
// now++;
// }
// assert(now==n);
// l.swap(t);
// }
// For(i,0,n-1) Answer(l[i],r[i]);
}
// void Solve(int32_t N) {
// int v = Query(1);
// for (int i = 1; i <= N; ++i) {
// Answer(i, 2 * N + 1 - i);
// }
// }
