#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
#include "minerals.h"
constexpr int maxn = 43007 * 2;
bool isIn[maxn];
int cntIn;
int n;
int myQuery(int i) {
if(isIn[i]) cntIn--;
else cntIn++;
isIn[i] = !isIn[i];
int ret = cntIn - Query(i + 1);
DC << " ============ Querying " << i << " -> " << ret << eol;
return ret;
}
unordered_set<int> surelyNot[maxn];
int curPairs;
void dq(vector<int> h1, vector<int> h2, bool in1) {
assert(h1.size() == h2.size());
DEBUG {
DC << "D&Q\n h1: {";
repIn(i, h1) DC << i << ", ";
DC << "}\n h2: {";
repIn(i, h2) DC << i << ", ";
DC << "}\n in1 " << in1 << " ; in2 " << eol;
repIn(i, h1) assert(isIn[i] == in1);
//repIn(i, h2) assert(isIn[i] == in2);
}
int sz = (int)h1.size(), m = sz / 2;
if(sz == 1) { Answer(h1.back() + 1, h2.back() + 1); return; }
/*
unordered_set<int> h1s, h2s;
repIn(i, h1) h1s.insert(i);
repIn(i, h2) h2s.insert(i);
vector<int> tmp;
while(h1s.size()) {
auto i = *h1s.begin();
h1s.erase(i);
int cntNot = 0;
repIn(j, h2s) cntNot += surelyNot[i].contains(j);
if(cntNot + 1 != h2s.size()) {
tmp.pb(i);
continue;
}
int theOne = -1;
repIn(j, h2s) if(!surelyNot[i].contains(j)) { theOne = j; break; }
Answer(i + 1, theOne + 1);
h2s.erase(theOne);
}
swap(h1, tmp);
h2.clear();
repIn(i, h2s) h2.pb(i);
h2s.clear();
sz = h1.size();
if(sz == 0) return;
if(sz == 1) { Answer(h1.back() + 1, h2.back() + 1); return; }
*/
int cntIn2 = 0;
repIn(i, h2) cntIn2 += isIn[i];
vector<int> lh1, lh2, rh1, rh2;
rep(i, 0, m) lh1.pb(h1[i]);
rep(i, m, sz) rh1.pb(h1[i]);
int toDel1 = -1, toDel2 = -1;
rep(i, in1 ? m : 0, in1 ? sz : m) {
auto newPairs = myQuery(h1[i]);
/*
if(newPairs == curPairs) repIn(j, h2) if(isIn[j]) surelyNot[h1[i]].insert(j), surelyNot[j].insert(h1[i]);
if(newPairs != curPairs) repIn(j, h2) if(!isIn[j]) surelyNot[h1[i]].insert(j), surelyNot[j].insert(h1[i]);
*/
if(newPairs != curPairs && cntIn2 == 1) {
int theOne = 0;
repIn(j, h2) if(isIn[j]) { theOne = j; break; }
Answer(h1[i] + 1, theOne + 1);
toDel1 = h1[i];
toDel2 = theOne;
}
if(newPairs == curPairs && cntIn2 + 1 == h2.size()) {
int theOne = 0;
repIn(j, h2) if(!isIn[j]) { theOne = j; break; }
Answer(h1[i] + 1, theOne + 1);
toDel1 = h1[i];
toDel2 = theOne;
}
curPairs = newPairs;
}
vector<int> tmp;
repIn(i, h1) if(i != toDel1) tmp.pb(i);
swap(tmp, h1);
tmp.clear();
repIn(i, lh1) if(i != toDel1) tmp.pb(i);
swap(tmp, lh1);
tmp.clear();
repIn(i, rh1) if(i != toDel1) tmp.pb(i);
swap(tmp, rh1);
tmp.clear();
repIn(i, h2) if(i != toDel2) tmp.pb(i);
swap(tmp, h2);
tmp.clear();
sz = h1.size();
if(sz == 0) return;
if(sz == 1) { Answer(h1.back() + 1, h2.back() + 1); return; }
repIn(i, h2) {
if(lh2.size() == lh1.size()) { rh2.pb(i); continue; }
if(rh2.size() == rh1.size()) { lh2.pb(i); continue; }
auto newPairs = myQuery(i);
if(newPairs != curPairs) lh2.pb(i);
else rh2.pb(i);
curPairs = newPairs;
}
dq(lh1, lh2, true);
dq(rh1, rh2, false);
}
void Solve(int N) {
n = N;
vector<int> firstHalf, secondHalf;
rep(i, 0, 2 * N) {
if((int)firstHalf.size() == n) { secondHalf.pb(i); continue; }
if((int)secondHalf.size() == n) { firstHalf.pb(i), curPairs = myQuery(i); continue; }
auto newPairs = myQuery(i);
if(newPairs != curPairs) secondHalf.pb(i);
else firstHalf.pb(i);
curPairs = newPairs;
if(firstHalf.size() == secondHalf.size()) dq(firstHalf, secondHalf, 1), n -= firstHalf.size(), firstHalf.clear(), secondHalf.clear();
}
dq(firstHalf, secondHalf, 1);
}
