#include "doll.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector<int> C,X,Y;
bool state[400005];
const int INF=1e9;
int newnode()
{
X.pb(INF),Y.pb(INF);
return -(int)(X.size());
}
int node(int x)
{
if(x==2) return newnode();
int tmp=newnode();
int a=node(x/2),b=node(x/2);
X[-tmp-1]=a,Y[-tmp-1]=b;
return tmp;
}
void walk(vector<int> &v,int st)
{
int k=0;
int pos=st;
while(k<v.size())
{
state[-pos] = !state[-pos];
if(state[-pos])
if(X[-(1+pos)]!=INF) pos=X[-(1+pos)];
else X[-(1+pos)]=v[k++],pos=st;
else
if(Y[-(1+pos)]!=INF) pos=Y[-(1+pos)];
else Y[-(1+pos)]=v[k++],pos=st;
}
}
int r_node(vector<int> &v)
{
int tmp,sz=v.size();
if(!(sz&(sz-1))) tmp=node(sz);
else
{
int nw=tmp=newnode(),lb=sz&-sz,a;
for(int i=1<<__lg(sz);i>lb;i>>=1)
{
if(v.size()&i)
a=node(i),X[-nw-1]=a;
else
X[-nw-1]=tmp;
a=newnode(),Y[-nw-1]=a,nw=Y[-nw-1];
}
X[-nw-1]=tmp;
if(lb>1) a=node(lb),Y[-nw-1]=a;
}
walk(v,tmp);
return tmp;
}
void create_circuit(int M, std::vector<int> A) {
C.resize(M+1);
C[0]=A[0];
if(A.size()==1)
C[1]=0;
else
{
for(int i=0;i+1<A.size();++i)
A[i]=A[i+1];
A.back()=0;
int tmp=r_node(A);
for(int i=0;i<A.size();++i)
C[i+1]=tmp;
}
answer(C,X,Y);
}
