#include "minerals.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int n){
long long x = rng();
return abs(x) % n;
}
void Answer(int x, int y);
int Query(int x);
vector<pair<vector<int> , vector<int>>> vec;
set<int> st;
int lst;
int ask(int x){
lst = Query(x);
if(st.find(x) == st.end()) st.insert(x);
else st.erase(x);
//for(auto to : st) cout << to << ' ';
//cout << '\n';
return lst;
}
void clr(){
for(auto to : st) ask(to);
st.clear();
return ;
}
void f(vector<int> v){
if(v.size() == 0){
return ;
}
if(v.size() == 2){
vec.push_back({{v[0]} , {v[1]}});
return ;
}
for(auto to : v){
// cout << to << ' ';
}
//cout << '\n';
int sz = v.size();
set<int> s1 , s2;
for(int i = 0;i < sz / 2; ++ i){
s1.insert(v[i]);
if(st.find(v[i]) == st.end()) ask(v[i]);
}
for(int i = sz / 2; i < sz; ++ i) s2.insert(v[i]);
for(auto to : s2){
if(st.find(to) != st.end()) ask(to);
}
vector<int> nv1 , nv2 , v1 , v2;
for(auto to : s2){
int ls = lst , x = ask(to);
if(ls == x) {
v2.push_back(to);
}
else{
nv2.push_back(to);
ask(to);
}
}
for(auto to : s1) ask(to);
for(auto to : s1){
int ls = lst , x = ask(to);
if(ls == x){
v1.push_back(to);
}
else{
nv1.push_back(to);
ask(to);
}
}
//cout << v1.size() << ' ' << v2.size() << '\n';
vec.push_back({v1 , v2});
f(nv2) , f(nv1);
}
void ans(vector<int> p , vector<int> q){
if(p.size() == 0) return ;
if(p.size() == 1){
Answer(p[0] , q[0]);
return ;
}
int sz = p.size();
set<int> s1 , s2;
vector<int> np1 , nq1 , np2 , nq2;
for(int i = 0;i < sz / 2; ++ i){
if(st.find(q[i]) == st.end()) ask(q[i]);
nq1.push_back(q[i]);
}
for(int i = sz / 2; i < sz; ++ i){
if(st.find(q[i]) != st.end()) ask(q[i]);
nq2.push_back(q[i]);
}
for(int i = 0; i < sz; ++ i){
int ls = lst , nw = ask(p[i]);
if(ls == nw) np1.push_back(p[i]);
else np2.push_back(p[i]);
}
//cout << -1;
ans(np1 , nq1);
ans(np2 , nq2);
}
void Solve(int N) {
vector<int> ff;
for(int i = 1;i <= 2 * N; ++ i) ff.push_back(i);
for(int i = 0;i < 2 * N; ++ i) swap(ff[i] , ff[rand(2 * N)]);
f(ff);
for(auto to : vec){
ans(to.fi , to.se);
}
}
