#include "minerals.h"
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
const int maxn=43005;
int x,out_id[2][maxn];
bool a[2][maxn];
inline bool query(int id1, int id2){
int y=Query(out_id[id1][id2]);
a[id1][id2]^=1;
bool flag=x!=y;
x=y;
return flag;
}
void Solve(int n){
x=0;
int cur1=0,cur2=0;
rep(2*n){
int y=Query(i+1);
if(y>x){
out_id[0][cur1++]=i+1;
}
else{
out_id[1][cur2++]=i+1;
}
x=y;
}
assert(cur1==n&&cur2==n);
rep(n) a[0][i]=1;
vector<vector<int>> vec;
vec.pb({});
rep(n) vec.back().pb(i);
mt19937 rng(7777714);
shuffle(all(vec.back()),rng);
rep1(_,16){
if(sz(vec)==n) break;
int cur=0;
vector<int> vec1;
for(auto& vv: vec){
if(sz(vv)==1){
cur++;
continue;
}
int s;
if(a[1][cur]) s=(sz(vv)+1)/2;
else s=sz(vv)/2;
vec1.pb(s);
rep(sz(vv)){
if(i<s&&!a[1][cur+i]) query(1,cur+i);
if(i>=s&&a[1][cur+i]) query(1,cur+i);
}
cur+=sz(vv);
}
reverse(all(vec1));
assert(cur==n);
vector<vector<int>> nvec;
for(auto& vv: vec){
if(sz(vv)==1){
nvec.pb(vv);
continue;
}
int s=vec1.back();
vec1.pop_back();
bool good[sz(vv)];
memset(good,0,sizeof good);
nvec.pb({});
int goodcnt=0,badcnt=0;
rep(sz(vv)){
if(goodcnt==s) good[i]=0;
else if(badcnt==sz(vv)-s) good[i]=1;
else good[i]=query(0,vv[i]);
if(good[i]) goodcnt++;
else badcnt++;
}
rep(sz(vv)) if(good[i]) nvec.back().pb(vv[i]);
assert(sz(nvec.back())==s);
nvec.pb({});
rep(sz(vv)) if(!good[i]) nvec.back().pb(vv[i]);
assert(sz(nvec.back())==sz(vv)-s);
}
vec=nvec;
}
assert(sz(vec)==n);
rep(n){
Answer(out_id[1][i],out_id[0][vec[i][0]]);
}
}
