#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e5;
ll S = 0, leaf = 0;
int L[MAXN+5], R[MAXN+5], is_leaf[MAXN+5], state[MAXN+5];
int construct(ll now, ll sisa) {
if (sisa == 1) {
is_leaf[++leaf] = 1;
return leaf;
}
else {
ll cur = ++S;
if (now > sisa / 2) {
R[cur-1] = construct(sisa/2, sisa/2);
L[cur-1] = construct(now-sisa/2, sisa/2);
}
else {
R[cur-1] = construct(now, sisa/2);
L[cur-1] = -1;
}
return -cur;
}
}
int sim(ll idx) {
if (idx >= 0) return idx;
idx *= -1;
state[idx-1] ^= 1;
if (state[idx-1]) return sim(L[idx-1]);
return sim(R[idx-1]);
}
void create_circuit(int M, vector<int> A) {
ll N = A.size();
ll sisa = 1;
N++;
while (sisa < N) sisa *= 2LL;
vector <int> id(N), C(M+1);
// semua terhubung sama the main root
for (int i = 0; i < M+1; i++) C[i] = -1;
construct(N, sisa);
A.push_back(0);
for (int i = 0; i < N; i++) {
int cur = sim(-1);
id[cur-1] = A[i];
}
vector <int> X, Y;
for (int i = 0; i < S; i++) {
ll lf = (L[i] >= 0 ? id[L[i]-1] : L[i]);
ll rg = (R[i] >= 0 ? id[R[i]-1] : R[i]);
X.push_back(lf);
Y.push_back(rg);
// cout << lf << " " << rg << "\n";
}
answer(C, X, Y);
}
