#include<iostream>
#include<vector>
#include<cmath>
#include "doll.h"
using namespace std;
vector<int>x,y,c,state,a;
int NN;
int nodes;
void new_node()
{
nodes++;
x.push_back(0);y.push_back(0);state.push_back(0);
}
void power2(int bit,int cur)
{
if(bit>1)
{
new_node();
x[cur-1]=-nodes;
power2(bit-1,nodes);
new_node();
y[cur-1]=-nodes;
power2(bit-1,nodes);
}
else
{
x[cur-1]=0;y[cur-1]=0;
}
}
void create(int n,int bit,int par)
{
new_node();
int cur=nodes;
if(par!=0)
{
y[par-1]=-cur;
}
if(bit==0)
{
if(n%2==1)x[cur-1]=0;
else x[cur-1]=-1;
y[cur-1]=0;///should be the last
return;
}
if(((1<<bit)&(n))!=0)
{
new_node();
x[cur-1]=-nodes;
power2(bit,nodes);
}
else
{
x[cur-1]=-1;
}
create(n,bit-1,cur);
}
int idx;
int curnode;
int statesX;
void run()
{
while(1)
{
int id=(-curnode)-1;
int nxtnode;
if(state[id]==0)
{
nxtnode=x[id];
state[id]=1;
statesX--;
}
else
{
nxtnode=y[id];
state[id]=0;
statesX++;
}
if(nxtnode==-1)break;
if(nxtnode==0)
{
if(state[id]==1)
{
x[id]=a[idx];
}
else
{
y[id]=a[idx];
}
idx++;
break;
}
curnode=nxtnode;
}
}
void simu()
{
a.push_back(0);
idx=0;
statesX=nodes;
do
{
curnode=-1;
run();
}while(statesX!=nodes);
}
void create_circuit(int M, std::vector<int> A)
{
a=A;
NN=a.size();
c.resize(M+1);
for(int i=0;i<=M;i++)c[i]=-1;
int bb;
for(int bit=20;bit>=0;bit--)
{
if((1<<bit)<=NN)
{
bb=bit;
break;
}
}
create(NN,bb,0);
simu();
answer(c,x,y);
}
