#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const ld p=0.3812;
mt19937 rng(time(0));
set<int>minerals;
int diff;
void Insert(int i){
if(minerals.find(i)!=minerals.end())exit(-1);
minerals.insert(i);
diff=Query(i);
}
void Erase(int i){
if(minerals.find(i)==minerals.end())exit(-1);
minerals.erase(i);
diff=Query(i);
}
void Toggle(int i){
if(minerals.find(i)==minerals.end())Insert(i);
else Erase(i);
}
bool Get(int i){return minerals.find(i)!=minerals.end();}
bool Pair(int i){
int diff1=diff;
if(!Get(i)){
Insert(i);
return diff==diff1;
}
else{
Erase(i);
return diff==diff1;
}
}
vector<pair<int,int>>Solve(vector<int>a,vector<int>b){
shuffle(a.begin(),a.end(),rng);
shuffle(b.begin(),b.end(),rng);
if(a.size()==1)return{{a[0],b[0]}};
if(a.size()==2){
if(Get(a[0])^Get(a[1])==0&&Get(b[0])^Get(b[1])==0)Toggle(a[0]);
if(Get(a[0])^Get(a[1])){
if(Pair(b[0])^Get(a[1])==0)swap(b[0],b[1]);
}
else{
if(Pair(a[0])^Get(b[1])==0)swap(b[0],b[1]);
}
return{{a[0],b[0]},{a[1],b[1]}};
}
int n=a.size(),m=p*n;
if(n<=6)m=n+1>>1;
vector<int>A1,A2,B1,B2;
for(auto i:a){
if(Get(i))A1.pb(i);
else A2.pb(i);
}
while(A1.size()<m){
int i=A2.back();A2.pop_back();
Toggle(i);
A1.pb(i);
}
while(A2.size()<m){
int i=A1.back();A1.pop_back();
Toggle(i);
A2.pb(i);
}
if(A1.size()<=A2.size()){
while(A1.size()>m){
int i=A1.back();A1.pop_back();
Toggle(i);
A2.pb(i);
}
}
else{
while(A2.size()>m){
int i=A2.back();A2.pop_back();
Toggle(i);
A1.pb(i);
}
}
for(int i=0;i<n;i++){
if(B1.size()==A1.size()){
while(i<n)B2.pb(b[i++]);
break;
}
if(B2.size()==A2.size()){
while(i<n)B1.pb(b[i++]);
break;
}
if(Pair(b[i]))B1.pb(b[i]);
else B2.pb(b[i]);
}
vector<pair<int,int>>res=Solve(A1,B1);
for(auto i:Solve(A2,B2))res.pb(i);
return res;
}
void Solve(int n){
vector<int>a,b;
for(int i=1;i<=2*n;i++){
int diff1=diff;
Insert(i);
if(diff==diff1)b.pb(i);
else a.pb(i);
}
for(auto [x,y]:Solve(a,b))Answer(x,y);
}
