#include "doll.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, mx, d;
int cur=-1;
vector<int> c, x, y;
vector<int> a;
bool cury[500500];
void build2(int val){
if (val==2){
x[-cur]=1e9;
y[-cur]=1e9;
cur--;
return;
}
int vpos=-cur;
cur--;
x[vpos]=cur;
val >>= 1;
build2(val);
y[vpos]=cur;
build2(val);
}
void build1(int val){
//printf("%d\n", val);
if (val==2){
x[-cur]=1e9;
if (d&1) y[-cur]=-1;
else y[-cur]=1e9;
cur--;
return;
}
int vpos=-cur;
cur--;
x[vpos]=cur;
val >>= 1;
build1(val);
if (val&d) y[vpos]=-1;
else{
y[vpos]=cur;
build2(val);
}
}
void check(){
c[0]=a[0];
int pos=a[0], idx=1, prev;
while(pos){
//printf("%d\n", pos);
prev=pos;
if (pos<0){
if (!cury[-pos]){
if (x[-pos]==1e9){
x[-pos]=a[idx];
pos=a[idx++];
}
else pos=x[-pos];
cury[-prev]=!(cury[-prev]);
}
else{
if (y[-pos]==1e9){
y[-pos]=a[idx];
pos=a[idx++];
}
else pos=y[-pos];
cury[-prev]=!(cury[-prev]);
}
}
else pos=-1;
}
}
void create_circuit(int M, vector<int> A){
n=A.size();
a.resize(n+1, 0);
for (int i=0;i<n;i++) a[i]=A[i];
a[n]=0;
for (int i=1<<30;i>0;i>>=1){
if (i&n){
mx=i<<1; break;
}
}
if (__builtin_popcount(n)==1) mx >>= 1;
d=mx-n;
c.resize(M+1, 0);
x.resize(2*n, 1e9);
y.resize(2*n, 1e9);
build1(mx);
//printf("%d\n", x[4]);
for (int i=1;i<=M;i++) c[i]=-1;
check();
int i;
for (i=n+99;i>=0;i--){
if (x[i]!=1e9) break;
}
vector<int> Rx(i), Ry(i);
for (int k=0;k<i;k++){
Rx[k]=x[k+1];
Ry[k]=y[k+1];
}
answer(c, Rx, Ry);
}
