#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 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 num[50005];
int best[50005];
int CURR=0;
bool same(int x){
int temp=Query(x);
int res=CURR==temp;
CURR=temp;
return res;
}
int n;
void solve(vector<int> l,vector<int> r,bool in){
int n=sz(l);
if (n==0) return;
if (n==1){
Answer(l[0],r[0]);
}
else{
vector<int> l1,l2;
vector<int> r1,r2;
rep(x,0,best[n]) l1.pub(l[x]);
rep(x,best[n],n) l2.pub(l[x]);
for (auto it:l1) same(it);
for (auto it:r){
if (sz(l1)==sz(r1)) r2.pub(it);
else if (sz(l2)==sz(r2)) r1.pub(it);
else if (same(it) != in) r1.pub(it);
else r2.pub(it);
}
solve(l1,r1,!in);
solve(l2,r2,in);
}
}
vector<int> get(vector<int> v){
vector<int> l,r;
rep(x,0,sz(v)){
if (same(v[x])) r.pub(v[x]);
else l.pub(v[x]);
}
vector<int> good,bad;
for (auto it:l){
if (same(it)) good.pub(it);
else bad.pub(it);
}
solve(good,r,false);
return bad;
}
void Solve(signed N) {
num[1]=0;
rep(x,2,50005){
num[x]=1e9;
int l=max(1LL,(int)(x*0.25)),r=min(x,(int)(x*0.4)+2);
rep(y,l,r) if (num[x]>num[y]+num[x-y]+x+y){
num[x]=num[y]+num[x-y]+x+y;
best[x]=y;
}
}
n=N;
vector<int> idx;
rep(x,1,2*n+1) idx.pub(x);
shuffle(all(idx),rng);
vector<int> l,r;
rep(x,0,n) l.pub(idx[x]);
rep(x,n,2*n) r.pub(idx[x]);
solve(get(l),get(r),false);
}
