#include "doll.h"
#include<vector>
#include<iostream>
#include<cassert>
#define MAXN 200005
using namespace std;
int N, L, V=-1, id;
bool state[MAXN];
vector<int> X, Y, C, Seq;
int build(int x, int d) {
if (x == 1 && d == 0) {
return(69);
} else if (x == 0) {return(-1);}
assert(d > 0);
int cur = V;
V--;
X[-cur-1] = build(x-min(x,(1<<(d-1))), d-1);
Y[-cur-1] = build(min(x,(1<<(d-1))), d-1);
return(cur);
}
int log(int x) {
return(x <= 1 ? 0 : log(x/2) + 1);
}
void simulate(int u) {
if (id == N+1) {return;}
if (state[-u] == 0) {
state[-u] = 1;
if (X[-u-1] == 69) {
X[-u-1] = Seq[id];
id++;
simulate(-1);
} else {
simulate(X[-u-1]);
}
} else {
state[-u] = 0;
if (Y[-u-1] == 69) {
Y[-u-1] = Seq[id];
id++;
simulate(-1);
} else {
simulate(Y[-u-1]);
}
}
}
void create_circuit(int M, std::vector<int> A) {
N = A.size(), L = log(N+1);
if ((1<<L) < N+1) {L++;}
for (int i=0; i<=M; i++) {
C.push_back(-1);
}
for (int i=0; i<N+L; i++) {
X.push_back(0);
Y.push_back(0);
}
Seq = A;
Seq.push_back(0);
build(N+1, L);
while (X.back() == 0 && Y.back() == 0) {
X.pop_back();
Y.pop_back();
}
simulate(-1);
answer(C, X, Y);
}
