#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#include "doll.h"
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = (int)5e5 + 10;
int lst = 0;
vector<int>trans[N];
int m;
int x[N],y[N];
int build(vector<int>k){
if(sz(k) == 1){
if(k[0] < 0){
x[lst]=lst;
y[lst]=-k[0];
lst++;
return lst-1;
}
return k[0];
}
// assert(sz(k) != 0);
int v = lst++;
vector<int>st[2];
if(sz(k) % 2 != 0)
k.insert(k.begin(), -v);
for(int i = 0; i < sz(k); ++i)
st[i&1].pb(k[i]);
// if(sz(st[0])>sz(st[1])){
// st[1].insert(st[1].begin(),-1);
// }
int A=build(st[0]),B=build(st[1]);
x[v]=A;
y[v]=B;
return v;
}
int code(int f){
if(f <= m)
return f;
return -(f-m);
}
bool good(int f){
int pw=1;
int F = f;
while(f){
f>>=1;
pw<<=1;
}
pw>>=1;
if(pw==F)
return true;
return false;
}
void create_circuit(int M, std::vector<int> A){
m = M;
A.push_back(0);
A.insert(A.begin(), 0);
for(int i = 0; i < sz(A) - 1; ++i){
trans[A[i]].push_back(A[i + 1]);
}
lst = M + 1;
vector < int > C(M + 1);
for(int i = 0; i <= M; ++i){
if(sz(trans[i]) == 0)
continue;
// reverse(all(trans[i]));
// while(!good(sz(trans[i]))){
// trans[i].pb(-1);
// }
// reverse(all(trans[i]));
// cout << " SZ " << sz(trans[i]) << endl;
if(sz(trans[i]) == 1){
C[i] = trans[i][0];
}else{
C[i] = code(build(trans[i]));
}
}
vector<int>X(lst-1-M),Y(lst-1-M);
for(int f=0;f<sz(X);++f){
X[f]=code(x[M+1+f]);
Y[f]=code(y[M+1+f]);
}
// cout << "LOL \n";
// for(int i = 0; i <= M; ++i)
// cout << C[i] << '\n';
// for(int f = 0; f < sz(X); ++f){
// cout << X[f] << ' ' << Y[f] << endl;
// }
// cout << endl;
assert(sz(X) <= 2 * N);
answer(C,X,Y);
}
/*
4 6
1 2 1 3 1 4
*/
