#include "minerals.h"
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using ii = pair<int, int>;
using iii = pair<int, ii>;
constexpr int MAXN = 43000;
constexpr int INF = 1e18 + 5;
constexpr int LOG = 20;
int V;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
vector<ii> pairs;
vector<int> state(2 * MAXN + 1);
int Qry(int x) {
state[x] ^= 1;
return Query(x);
}
int dnc(int unq, vector<int> v1, vector<int> v2) {
/*
for (int i : v1) cout << i << ' '; cout << '\n';
for (int i : v2) cout << i << ' '; cout << '\n';
for (int i = 1; i <= 2 * V; ++i) cout << state[i] << ' '; cout << '\n';
*/
int sz = v1.size();
if (sz == 0) {
return unq;
}
if (sz == 1) {
pairs.emplace_back(v1[0], v2[0]);
return unq;
}
shuffle(v1.begin(), v1.end(), rng);
shuffle(v2.begin(), v2.end(), rng);
vector<int> v1a; vector<int> v1b; vector<int> v2a; vector<int> v2b;
bool flip = state[v1[0]];
int spl = max(int(sz * 0.38), 1ll);
for (int i = 0; i < spl; ++i) {
unq = Qry(v1[i]);
v1a.emplace_back(v1[i]);
}
for (int i = spl; i < sz; ++i) v1b.emplace_back(v1[i]);
for (int i = 0; i < sz; ++i) {
if (v2a.size() == spl) {
v2b.emplace_back(v2[i]);
continue;
}
if (v2b.size() == sz - spl) {
v2a.emplace_back(v2[i]);
continue;
}
int curr = Qry(v2[i]);
if (flip ^ (curr == unq)) {
v2a.emplace_back(v2[i]);
}
else {
v2b.emplace_back(v2[i]);
}
unq = curr;
}
unq = dnc(unq, v1a, v2a);
unq = dnc(unq, v1b, v2b);
return unq;
}
void Solve(signed N) {
V = N;
int last = 0;
vector<int> v1;
vector<int> v2;
for (int i = 1; i <= 2 * N; ++i) {
int curr = Qry(i);
if (last != curr) {
v1.emplace_back(i);
}
else v2.emplace_back(i);
last = curr;
}
dnc(N, v1, v2);
for (auto p : pairs) Answer(p.first, p.second);
}
/*
4
1 5
2 6
3 4
7 8
*/
