#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50;
vector<int>C,X,Y;
vector<int>susedni[N];
int LOG[2*N+50];
int S;
void Resi(int &c,int ss,int se,int broj,int rt,vector<int>&a){
if(broj-1>=se){c=rt;return;}
c=-(++S);int ind=S;
if(ss+1==se){
int n=a.size();
int k=ss>>1,L=LOG[n]-1;
vector<int>bits;
while(L--) bits.pb(k&1),k>>=1;
k=0;for(int i=bits.size()-1,e=1;i>=0;i--,e<<=1) if(bits[i]) k+=e;
X[ind]=a[k];
Y[ind]=a[k+n/2];
//printf("%i %i %i: %i %i\n",ss,se,c,X[ind],Y[ind]);
return;
}
int mid=ss+se>>1;
Resi(X[ind],ss,mid,broj,rt,a);
Resi(Y[ind],mid+1,se,broj,rt,a);
//printf("%i %i %i: %i %i\n",ss,se,c,X[ind],Y[ind]);
}
void create_circuit(int m,vector<int> A) {
for(int i=1,e=1,ct=-1;i<=2*N;i++){if(i==e)e<<=1,ct++;LOG[i]=ct;}
A.pb(0);int n=A.size();
for(int i=0;i<m+1;i++) C.pb(0);
C[0]=A[0];
X.pb(0),Y.pb(0);
X.resize(5*N),Y.resize(5*N);
for(int i=0;i<n;i++) susedni[A[i]].pb(A[i+1]);
for(int i=1;i<=m;i++){
int k=susedni[i].size();
if(k==1) C[i]=susedni[i][0];
if(k<=1) continue;
int ct=0;
for(int j=0,e=1;j<=29;j++,e<<=1) if(e>=k){ct=e-k,k=e;break;}
vector<int>temp(k,0);
for(int j=0,ind=ct;j<k/2;j++){
vector<int>bits;int L=LOG[k]-1,K=j;
while(L--) bits.pb(K&1),K>>=1;
K=0;for(int i=bits.size()-1,e=1;i>=0;i--,e<<=1) if(bits[i]) K+=e;
if(ind)temp[K]=-S-1,ind--;
if(ind)temp[K+k/2]=-S-1,ind--;
}
for(int j=0,ind=0;j<k;j++){
if(temp[j]==0) temp[j]=susedni[i][ind++];
}
/*reverse(susedni[i].begin(),susedni[i].end());
while(susedni[i].size()<k) susedni[i].pb(-S-1);
reverse(susedni[i].begin(),susedni[i].end());*/
//printf("%i: ",i);for(auto j:temp) printf("%i ",j);printf("\n");
Resi(C[i],0,k-1,ct,-S-1,temp);
}
//for(auto &i:X) i=-i;
//for(auto &i:Y) i=-i;
while(X.size()>S+1) X.pop_back();
while(Y.size()>S+1) Y.pop_back();
reverse(X.begin(),X.end());X.pop_back();reverse(X.begin(),X.end());
reverse(Y.begin(),Y.end());Y.pop_back();reverse(Y.begin(),Y.end());
answer(C, X, Y);
}
