#include "doll.h"
#include <bits/stdc++.h>
#define maxn 400005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int N, nho, nt, cnt;
vector<int> a, X, Y;
int parity[maxn];
int build(int lo, int hi) {
if (nho >= hi-lo+1) {
nho -= hi-lo+1;
return 1;
}
if (lo == hi)
return INT_MAX/2;
int mid = (lo + hi) >> 1, cur = ++nt;
X[cur-1] = -build(lo, mid);
Y[cur-1] = -build(mid+1, hi);
return cur;
}
void dfs(int u, int lo, int hi) {
if (lo == hi) {
X[u-1] = a[cnt]; ++cnt;
return;
}
int next_destination = (parity[u] ? -Y[u-1] : -X[u-1]);
parity[u] ^= 1;
if (next_destination == 1) return;
int mid = (lo + hi) >> 1;
if (next_destination == -X[u-1]) {
if (lo == mid) {
X[u-1] = a[cnt]; ++cnt;
return;
}
dfs(next_destination, lo, mid);
}
else {
if (mid+1 == hi) {
Y[u-1] = a[cnt]; ++cnt;
return;
}
dfs(next_destination, mid+1, hi);
}
}
void create_circuit(int M, vector<int> A) {
N = A.size();
a = A; nt = cnt = 0;
if (N == 1) {
vector<int> C(M+1, 0);
C[0] = A[0];
C[A[0]] = 0;
answer(C, {}, {});
return;
}
int k = __lg(N) + 1;
nho = (1<<k)-N-1;
vector<int> C(M+1, -1);
++nt;
X.assign(N + __lg(N+1) + 100, -1);
Y.assign(N + __lg(N+1) + 100, -1);
X[0] = -build(0, (1<<k)/2-1);
Y[0] = -build((1<<k)/2, (1<<k)-1);
a.emplace_back(0);
X.resize(nt);
Y.resize(nt);
for (int i = 1; i <= nt; i++) parity[i] = 0;
for (int i = 0; i < (1<<k); i++) dfs(1, 0, (1<<k)-1);
answer(C, X, Y);
}
/*
4 4
1 2 1 3
*/
