#include "doll.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
const int MN = 2e5;
int S;
std::vector<int> X, Y;
bool root[MN], state[MN];
void dfs(int &n, int l, int r, int qr)
{
n=++S; X.push_back(0), Y.push_back(0);
if(r-l>2)
{
int m=l+(r-l)/2;
dfs(X[n-1], l, m, qr);
if(m < qr) dfs(Y[n-1], m, r, qr);
}
else
root[n]=1;
}
void create_circuit(int M, std::vector<int> A) {
X.reserve(MN);
Y.reserve(MN);
int N = A.size();
std::vector<int> C(M + 1);
C[0]=A[0];
if(N==1)
{
C[C[0]]=0;
answer(C, X, Y);
return;
}
for(int i=1;i<=M;++i)
C[i]=-1;
//for(auto x:A) printf("%d ", x); printf("\n");
std::rotate(A.begin(), A.begin()+1, A.end());
//for(auto x:A) printf("%d ", x); printf("\n");
A.back()=0;
if(A.size()&1)
A.insert(A.begin(), -1);
int d = 31 - __builtin_clz((int)A.size()-1);
assert((1<<d+1) >= A.size() && A.size() > (1<<d));
int top;
dfs(top, 0, N, A.size());
for(int& x:X) x*=-1;
for(int& x:Y) x*=-1;
int ctr=0;
int n=-top;
for(;n != 0;)
{
if(n > 0)
n = -top;
else if(root[-n])
{
state[-n] ^= 1;
assert(ctr < A.size());
n = (state[-n] ? X[-n-1] : Y[-n-1]) = A[ctr++];
}
else
{
state[-n] ^= 1;
n = state[-n] ? X[-n-1] : Y[-n-1];
}
}
//printf("%d %lu\n", ctr, A.size());
assert(ctr == A.size());
answer(C, X, Y);
}
