#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = -1;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
vector<int> v1,v2;
set<int> s1,s2;
set<int> s;
vector<pair<int,int>> out;
int lst;
bool has(int x){
int q=Query(x);
bool can=(lst==q);
lst=q;
return can;
}
void dnc(vector<int> L, vector<int> R, bool boo){
assert(L.size()==R.size());
if(L.size() == 1 && R.size() == 1){
out.push_back({L[0],R[0]});
return;
}
int mi;
if(boo){
mi=round((0.62) * (double)R.size());
} else{
mi=round((0.38) * (double)R.size());
}
vector<int> Llf, Lrg, Rlf, Rrg;
unordered_set<int> w1;
for(int i=0;i<mi;i++){ // [0,mi) is the set i want to query
w1.insert(R[i]);
if(s.find(R[i]) == s.end()){
lst=Query(R[i]);
s.insert(R[i]);
}
}
vector<int> del;
for(auto x:s){
if(w1.find(x) == w1.end()){
del.push_back(x);
}
}
for(auto x:del){
lst=Query(x);
s.erase(x);
}
for(int i=0;i<(int)L.size()-1;i++){
int x=L[i];
bool hh=has(x);
if(hh){
Llf.push_back(x);
} else{
Lrg.push_back(x);
}
}
for(int i=0;i<mi;i++){
Rlf.push_back(R[i]);
}
for(int i=mi;i<(int)R.size();i++){
Rrg.push_back(R[i]);
}
if(Llf.size() != Rlf.size()){
Llf.push_back(L.back());
} else{
Lrg.push_back(L.back());
}
dnc(Llf,Rlf,1);
dnc(Lrg,Rrg,0);
}
void Solve(int N) {
n=N;
vector<int> idx;
for(int i=1;i<=2*n;i++){
idx.push_back(i);
}
shuffle(idx.begin(),idx.end(),rng);
for(int i=1;i<=2*n;i++){
int x=idx[i-1];
int q=Query(x);
if(q==lst){
v2.push_back(x);
} else{
v1.push_back(x);
}
lst=q;
}
for(auto x:v2){
s.insert(x);
}
dnc(v1,v2,1);
for(auto x:out){
Answer(x.first,x.second);
}
}
