#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int ls;
vector<int> c,sw[2],st;
int cv(int x){
return -x-1;
}
void build(int cr,int s){
if(s==1)return;
sw[0][cr]=cv(++ls);
sw[0].push_back(0);sw[1].push_back(0);st.push_back(0);
build(ls,s-1);
sw[1][cr]=cv(++ls);
sw[0].push_back(0);sw[1].push_back(0);st.push_back(0);
build(ls,s-1);
}
int* sim(int cr,int s){
st[cr]^=1;
if(s==1)return &(sw[st[cr]^1][cr]);
return sim(cv(sw[st[cr]^1][cr]),s-1);
}
void create_circuit(int m, std::vector<int> a) {
int n=a.size();
vector<int> ot[m+1];
ot[0].push_back(a[0]);
for(int i=0;i<n-1;i++)ot[a[i]].push_back(a[i+1]);
ot[a[n-1]].push_back(0);
c.resize(m+1);
ls=-1;
for(int i=0;i<=m;i++){
if(ot[i].empty())c[i]=i;
else if(ot[i].size()==1){
c[i]=ot[i][0];
}else{
int s=1;
while((1<<s)<ot[i].size())s++;
c[i]=cv(++ls);
sw[0].push_back(0);sw[1].push_back(0);st.push_back(0);
int sr=ls;
build(ls,s);
for(int t=0;t<(1<<s);t++){
int *x=sim(sr,s);
if(t<ot[i].size()-1){
*x=ot[i][t];
}else if(t==(1<<s)-1){
*x=ot[i].back();
}else{
*x=cv(sr);
}
}
}
}
answer(c,sw[0],sw[1]);
}
