#include "doll.h"
using namespace std;
#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
int rev_bit(int x, int l){
int y=0;
for (int i=0;i<l;i++){
y=y*2+x%2;
x/=2;
}
return y;
}
int ind_to_x(int i){
return -i-1;
}
int gen(vi& X, vi& Y, vi& dest){
int n=1;while(n<dest.size())n*=2;
int xi = X.size()-1;
vi dest2(n,ind_to_x(xi+1));
for (int i=0;i<dest.size()-1;i++)dest2[rev_bit(i,n)]=dest[i];
dest2[n-1] = dest.back();
for (int i=1;i<n/2;i++){
X.pb(ind_to_x(xi+i*2));
Y.pb(ind_to_x(xi+i*2+1));
}
for (int i=0;i<n;i+=2){
X.pb(dest2[i]);
Y.pb(dest2[i+1]);
}
return ind_to_x(xi+1);
}
void create_circuit(int m, std::vector<int> A) {
int n = A.size();
std::vector<int> C(m + 1);
vvi dest(m+1,vi());
for (int i=0;i<n-1;i++)dest[A[i]].pb(A[i+1]);
dest[A[n-1]].pb(0);
vi X,Y;
for (int i=1;i<=m;i++){
int ds=dest[i].size();
if (ds==0){
C[i]=0;
continue;
}
if (ds==1){
C[i] = dest[i][0];
continue;
}
C[i]=gen(X,Y,dest[i]);
}
C[0] = A[0];
answer(C, X, Y);
}
