#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector <int> C, X, Y, A;
void create_switch(vector <int> xd, int ind){
int nsc=xd.size();
if(nsc==0){
return;
}
if(nsc==1){
C[ind]=xd[0];
return;
}
vector <int> aguss;
int papa=-1;
int i=1;
while(i<2*nsc){
i*=2;
++papa;
}
i/=2;
int sp=X.size();
aguss.assign(i-nsc, -sp-1);
for(int j=i-nsc; j<i; ++j){
aguss.push_back(xd[j-i+nsc]);
}
xd=aguss;
nsc=i;
X.resize(X.size()+nsc-1);
Y.resize(Y.size()+nsc-1);
i=i/2-1;
C[ind]=-sp-1;
for(int j=0; j<i; ++j){
X[sp+j]=-sp-2*j-2;
Y[sp+j]=-sp-2*j-3;
}
for(int j=0; j<nsc; ++j){
int m=-sp;
int aux=j;
for(int potato=1; potato<papa; ++potato){
if(aux%2){
m=Y[-m]+1;
}
else{
m=X[-m]+1;
}
aux/=2;
}
if(aux%2){
Y[-m]=xd[j];
}
else{
X[-m]=xd[j];
}
}
sp+=nsc;
return;
}
void create_circuit(int xd, vector <int> dx){
M=xd+1;
dx.push_back(0);
N=dx.size();
A=dx;
C.assign(M, 0);
vector <vector <int> > conn;
conn.resize(M);
conn[0].push_back(A[0]);
for(int i=1; i<N; ++i){
conn[A[i-1]].push_back(A[i]);
}
for(int i=0; i<M; ++i){
create_switch(conn[i], i);
}
answer(C, X, Y);
return;
}
