#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 86005;
int n;
bool p[maxn];
int verd;
vector<pair<int,int>> ans;
int put(int x) {
int ori = verd;
verd = Query(x);
p[x] = !p[x];
// cout << "Q " << x << " " << verd << " " << ori << " " << verd - ori << endl;
return verd - ori;
}
void solve(vector<int> L, vector<int> R) {
int sz = L.size();
if (sz == 1) {
ans.push_back({L[0], R[0]});
return;
}
// cout << "TEST " << sz << endl;
// for (int i:L) cout << p[i] << " "; cout << endl;
// for (int i:R) cout << i << " "; cout << endl;
if (p[L[0]] == p[L[1]]) int trash = put(L[0]);
for (int i=1;i<sz/2;i++) int trash = put(L[i]);
// for (int i=1;i<=2*n;i++) cout << p[i] << " "; cout << endl;
vector<int> ll[2], rr[2];
for (int i:L) ll[p[i]].push_back(i);
for (int i=1;i<sz;i++) {
rr[!abs(put(R[i]))].push_back(R[i]);
}
if (rr[0].size() < ll[0].size()) {
rr[0].push_back(R[0]);
swap(rr[0][0], rr[0].back());
} else {
rr[1].push_back(R[0]);
swap(rr[1][0], rr[1].back());
}
solve(rr[0], ll[0]); solve(rr[1], ll[1]);
}
void Solve(int N) {
n = N, verd = 0;
ans.clear();
for (int i=1;i<=2*n;i++) p[i] = false;
vector<int> L, R;
for (int i=1;i<=2*n;i++) {
if (put(i)) R.push_back(i);
else L.push_back(i);
}
solve(L, R);
for (auto [x, y]:ans) Answer(x, y);
}
