#include "minerals.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
const int N = 1e5 + 500;
int kod[N], tp[N], P[N], ans[N];
int un[N], lst = 0, mks = 0, n;
vector < int > kol[20][N];
int pitaj(int x){
int nw = Query(x);
int ret = abs(lst - nw);
lst = nw; un[x] = !un[x];
return ret;
}
void pripremi(int l, int r, int raz){
if(l == r) return;
mks = max(mks, raz);
for(int i = l;i <= (l + r) / 2;i++)
kod[i] += (1 << raz);
pripremi(l, (l + r) / 2, raz + 1);
pripremi((l + r) / 2 + 1, r, raz + 1);
}
void odradi(int red){
for(int i = 1;i <= 2 * n;i++){
if(!tp[i] && (un[i] ^ (!!(P[i] & (1 << red)))))
pitaj(i);
}
for(int i = 1;i <= 2 * n;i++)
if(tp[i] && !ans[i]){
int odg = !pitaj(i);
P[i] += odg * (1 << red);
}
}
inline void mozda(int red){
for(int i = 1;i <= 2 * n;i++){
if(!tp[i] || ans[i]) continue;
//printf("i = %d P[i] = %d kol = %d\n", i, P[i], (int)kol[red][P[i]].size());
if(lower_bound(kol[red][P[i]].begin(), kol[red][P[i]].end(), i) + 1 == kol[red][P[i]].end()){
ans[i] = *lower_bound(kol[red][P[i]].begin(), kol[red][P[i]].end(), i);
// printf("nasao\n");
}
}
}
bool cmp(int x, int y){
return P[x] < P[y];
}
void Solve(int nn) {
n = nn;
pripremi(0, n - 1, 0);
int cur = 0;
for(int i = 1;i <= 2 * n;i++){
tp[i] = pitaj(i);
if(!tp[i]){
P[i] = kod[cur++];
for(int j = 0;j <= mks + 1;j++)
kol[j][P[i] & ((1 << j) - 1)].PB(i);
}
}
mozda(0);
for(int i = 0;i <= mks;i++){
odradi(i);
mozda(i + 1);
}
for(int i = 1;i <= 2 * n;i++){
//if(tp[i]) printf("%d %d\n", i, ans[i]);
if(tp[i]) Answer(i, ans[i]);
}
}
