#include <bits/stdc++.h>
#include "doll.h"
#pragma GCC optimize("O0")
using namespace std;
int n, m, c = -2;
vector<int> X, Y, mode;
void b(int u, int l, int &j){
if(l){
Y[-u-1] = c;
b(c--, l-1, j);
if(j){
X[-u-1] = c;
b(c--, l-1, j);
}
else X[-u-1] = -1;
}
else{
Y[-u-1] = m+1, j--;
if(j) X[-u-1] = m+1, j--;
else X[-u-1] = -1;
}
}
void asg(int u, int t){
if(mode[-u-1]){
mode[-u-1] = 0;
if(Y[-u-1] == m+1) Y[-u-1] = t;
else asg(Y[-u-1], t);
}
else{
mode[-u-1] = 1;
if(X[-u-1] == m+1) X[-u-1] = t;
else asg(X[-u-1], t);
}
}
void create_circuit(int M, vector<int> A){
auto K=A;
A.push_back(0);
n = A.size(), m = M;
vector<int> C(m+1);
X.resize(2*n), Y.resize(2*n), mode.resize(2*n);
C[0] = -1;
for(int i = 1; i <= m; i++) C[i] = -1;
int l = ceil(log2(n)), t = n;
b(-1, l-1, t);
for(int i = 0; i < n; i++) asg(-1, A[i]);
X.resize(-c-1), Y.resize(-c-1);
vector<bool>B(400000,false);
int p=0;
vector<int>T;
int cnt=0;
do{
cnt++;
if(p>=0){
if(p)T.push_back(p);
p=C[p];
}
else{
if(B[-p-1]){
B[-p-1]=!B[-p-1];
p=Y[-p-1];
}
else{
B[-p-1]=!B[-p-1];
p=X[-p-1];
}
}
}while(p);
assert(K==T);
bool f=false;
for(int i=0;i<400000;i++){
f|=B[i];
}
assert(!f);
for(int i:C){
assert(-(int)X.size()<=i&&i<=M);
}
for(int i:X){
assert(-(int)X.size()<=i&&i<=M);
}
for(int i:Y){
assert(-(int)X.size()<=i&&i<=M);
}
assert(cnt<=20000000);
answer(C, X, Y);
}
