#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = (int)(1e5+5);
#define sz(x) (int)(x.size())
int log_2(int x){
return 31-__builtin_clz(x);
}
vector<int> occ[MX],C;
bool state[4*MX],last[4*MX];
int idx=1,X[4*MX],Y[4*MX],a[2*MX];
// fix indexes 2*i is wrong, must assign indexes dynamically
void gimme(int x){
//sz(oc[x])==1
int nb=(1<<(log_2(sz(occ[x])-1)+1))-1;
int sum=0,st=idx+1,comp=0;
vector<int> vec={idx};
while((sum+sz(vec))< nb){
vector<int> G;
for(auto it:vec){
X[it]=-st;
G.push_back(st),st++;
Y[it]=-st;
G.push_back(st),st++;
}
sum+=sz(vec);
vec=G;
}
C[x]=-idx;
for (int i = idx; i <= idx+nb-1; ++i)
last[idx]=0;
for(auto it:vec)
last[it]=1;
for (int i = 0; i < nb+1; ++i)
{
int r=-idx;
while(!last[-r]){
state[-r]=(!state[-r]);
if(state[-r])r=X[-r];
else r=Y[-r];
}
if((nb-i)<sz(occ[x])){
/*cerr<<-r<<" ";
cerr<<a[occ[x][comp]+1]<<"\n";*/
//cerr<<nb-i<<"\n";
if(!state[-r])X[-r]=a[occ[x][comp]+1];
else Y[-r]=a[occ[x][comp]+1];
comp++;
}
else {
if(!state[-r])X[-r]=-idx;
else Y[-r]=-idx;
}
state[-r]=(!state[-r]);
}
/*for (int i = idx; i <= idx+nb-1; ++i)
cerr<<i<<" : "<<X[i]<<" "<<Y[i]<<"\n";
*/
idx+=nb;
}
void create_circuit(int M, vector<int> A) {
for (int i = 0; i < sz(A); ++i)
occ[A[i]].push_back(i),a[i]=A[i];
a[sz(A)]=0;
A.push_back(0);
C.resize(M+1);
C[0]=A[0];
for (int i = 0; i < sz(A)-1; ++i)
if(occ[A[i]][0]==i)
gimme(A[i]);
vector<int> x(idx-1),y(idx-1);
for (int i = 1; i < idx; ++i){
x[i-1]=X[i],y[i-1]=Y[i];
}
answer(C, x, y);
}
