#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int rev(int x, int sz) {
int k = 31 - __builtin_clz(sz);
int ret = 0;
for (int i=0; i<k; ++i) ret |= (1 << (k-1-i)) * ((x & (1 << i)) > 0);
// cout << x << ' ' << sz << ' ' << ret << endl;
return ret;
}
const int INF = 1e9;
int switch_cnt = 0;
vector<int> c, x, y;
int solve(int cnt, int lev) {
// cout << l << ' ' << r << ' ' << lev << endl;
int root = -switch_cnt-1;
switch_cnt++;
if (lev == 1) {
x.push_back((cnt == 1 ? -1 : INF));
y.push_back(INF);
return root;
}
if (cnt > (1 << (lev-1))) {
x.push_back(0);
y.push_back(0);
x[-root-1] = solve(cnt-(1<<(lev-1)), lev-1);
y[-root-1] = solve(1<<(lev-1), lev-1);
} else {
x.push_back(-1);
y.push_back(0);
y[-root-1] = solve(cnt, lev-1);
}
return root;
}
void create_circuit(int m, vector<int> A) {
int n = A.size();
A.push_back(0);
c.resize(m+1, -1);
int lev = 0;
while (n+1 > (1 << lev)) lev++;
solve(n+1, lev);
// for (int i: c) cout << i << ' ';
// cout << endl;
// for (int i: x) cout << i << ' ';
// cout << endl;
// for (int i: y) cout << i << ' ';
// cout << endl;
int curr = -1;
int allocate_cnt = 0;
vector<bool> state(x.size(), 0);
while (curr != 0) {
if (curr >= 0) curr = c[curr];
else {
int& nxt = (state[-curr-1] ? y[-curr-1] : x[-curr-1]);
if (nxt == INF) {
nxt = A[allocate_cnt++];
}
state[-curr-1] = !state[-curr-1];
curr = nxt;
}
// cout << curr << endl;
}
answer(c, x, y);
}
