#include "doll.h"
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
vector<int> destino[100006];
int X[4000006];
int Y[4000006];
int create_tree(int i,int limit,int lv,int sum,int n,int root,int trigger)
{
int last=i;
if(lv==limit-1){
int threshold=(1<<limit)-n;
if(sum<threshold)
X[(i+root-1)-1]=-root;
else
X[(i+root-1)-1]=destino[trigger][sum-threshold];
sum+=(1<<lv);
//debug(sum);
if(sum<threshold)
Y[(i+root-1)-1]=-root;
else
Y[(i+root-1)-1]=destino[trigger][sum-threshold];
}
else{
X[i+root-1-1]=-(2*i+root-1);
last=max(last,create_tree(i*2,limit,lv+1,sum,n,root,trigger));
Y[i+root-1-1]=-(2*i+root);
last=max(last,create_tree(i*2+1,limit,lv+1,sum+(1<<lv),n,root,trigger));
}
return last;
}
int log_n[400005];
int k;
void create_circuit(int m, vector<int> A) {
int n=A.size();
log_n[2]=1;
for(int i=3;i<=400000;i++){
log_n[i]=log_n[(i+1)/2]+1;
}
vector<int> C(m + 1);
C[0]=A[0];
for(int i=0;i<n-1;i++){
destino[ A[i] ].push_back(A[i+1]);
}
destino[ A[n-1] ].push_back(0);
for(int i=1;i<=m;i++){
if(destino[i].size()==0) C[i]=0;
else if(destino[i].size()==1) C[i]=destino[i][0];
else{
int limit=log_n[ destino[i].size() ];
C[i]=-(k+1);
k+=create_tree(1,limit,0,0,destino[i].size(),k+1,i);
//debug(k);
}
}
vector<int> x,y;
for(int i=0;i<k;i++){
x.push_back(X[i]);
y.push_back(Y[i]);
}
answer(C, x, y);
}
