#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 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> a , b;
for(int i = 1;i <= 2 * N; ++ i){
int ls = lst , x = ask(i);
if(ls != x) a.push_back(i);
else b.push_back(i);
}
for(int i = 0;i < a.size(); ++ i){
swap(a[i] , a[rand(N)]);
swap(b[i] , b[rand(N)]);
}
vec.push_back({a , b});
for(auto to : vec){
ans(to.fi , to.se);
}
}
