#include "doll.h"
#include <bits/stdc++.h>
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 8e5+15;
const int SQRT = 560;
const int INF = 1e9+10;
const int MOD = 998244353;
const int LOG = 20;
int n, m;
int a[MAXN], x[MAXN], y[MAXN], use[MAXN];
vector<int> C, X, Y;
int lg, node, num;
void dfs(int id, int dep){
if(dep == lg){
node++;
if(node > num-n) use[id] = 1;
else use[id] = 0;
return;
}
dfs(lf, dep+1); dfs(rg, dep+1);
use[id] = use[lf]+use[rg];
}
void trav(int id, int dep){
if(dep+1 == lg){
if(use[lf]) x[id] = lf;
else x[id] = -1;
if(use[rg]) y[id] = rg;
else y[id] = -1;
return;
}
if(!use[lf] && !use[rg]) return;
if(use[lf]) trav(lf, dep+1), x[id] = lf;
else x[id] = -1;
if(use[rg]) trav(rg, dep+1), y[id] = rg;
else y[id] = -1;
}
int name[MAXN], las[MAXN];
bool ty[MAXN];
int idx, tim;
int ansx[MAXN], ansy[MAXN];
void bd(int nw, int dep){
if(dep == lg) return;
++tim;
name[nw] = tim;
if(x[nw] != -1){
bd(x[nw], dep+1);
ansx[name[nw]] = name[x[nw]];
} else ansx[name[nw]] = -1;
if(y[nw] != -1){
bd(y[nw], dep+1);
ansy[name[nw]] = name[y[nw]];
} else ansy[name[nw]] = -1;
}
void move(int nw, int dep, int mask){
if(nw == -1){
int bit = lg-dep;
for(int i=0; i<(1<<bit); i++)
las[mask + (i<<dep)] = -1;
return;
}
if(dep == lg){ // nw -> mask
las[mask] = nw;
return;
// name[nw] = n+n+a[idx];
}
move(x[nw], dep+1, mask); move(y[nw], dep+1, mask+(1<<dep));
}
void create_circuit(int M, std::vector<int> A) {
n = A.size(); m = M;
for(int i=0; i<n; i++) a[i] = A[i];
a[n] = 0; n++;
num = 1;
while(num < n){
lg++; num *= 2;
}
C.resize(m+1);
for(int i=0; i<=m; i++) C[i] = -1;
dfs(1, 0);
trav(1,0);
// for(int i=1; i<=3; i++){
// cout << i << ' ' << x[i] << ' ' << y[i] << "xy\n";
// }
move(1, 0, 0);
for(int i=0; i<num; i++){ // mask ini akhirannya kemana
if(las[i] == -1) continue;
name[las[i]] = n+n+a[idx];
idx++;
}
bd(1, 0);
// cout << "xx\n";
X.resize(tim); Y.resize(tim);
for(int i=0; i<tim; i++){ //i+1 ke mana
X[i] = ansx[i+1], Y[i] = ansy[i+1];
if(X[i] != -1){
if(X[i] < n+n) X[i] = -X[i];
else X[i] -= n+n;
}
if(Y[i] != -1){
if(Y[i] < n+n) Y[i] = -Y[i];
else Y[i] -= n+n;
}
// cout << i+1 << ' ' << X[i] << ' ' << Y[i] << " pp\n";
}
answer(C, X, Y);
}
