#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int numNode, skiped;
vector<int> a, c, nxt[2], state, nodeInd;
vector<bool> mark;
void init(int id, int l, int r){
if (l + 1 == r){
mark[id] = (a[l] == -1 && a[r] == -1);
return;
}
int mid = (l + r) >> 1;
init(id << 1, l, mid);
init(id << 1 | 1, mid + 1, r);
mark[id] = mark[id << 1] && mark[id << 1 | 1];
}
void build(int id, int l, int r){
if (mark[id]){
skiped += r - l + 1;
return;
}
nodeInd[id] = ++numNode;
if (l + 1 == r)
return;
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
nxt[0][nodeInd[id] - 1] = mark[id << 1]? -1 : -nodeInd[id << 1];
nxt[1][nodeInd[id] - 1] = mark[id << 1 | 1]? -1 : -nodeInd[id << 1 | 1];
}
void create_circuit(int m, vector<int> _a) {
a = _a;
a.push_back(0);
reverse(a.begin(), a.end());
int n = 1;
while (n < (int) a.size())
n *= 2;
while ((int) a.size() < n)
a.push_back(-1);
reverse(a.begin(), a.end());
c.assign(m + 1, -1);
mark.assign(n, 0);
nodeInd.assign(n, 0);
nxt[0].assign(n, 0);
nxt[1].assign(n, 0);
state.assign(n, 0);
init(1, 0, n - 1);
build(1, 0, n - 1);
nxt[0].resize(numNode);
nxt[1].resize(numNode);
state.resize(numNode);
for(int i = skiped; i < n; i++){
int ind = a[i], cur = 1;
while (nxt[state[cur - 1]][cur - 1] < 0){
int tmp = -nxt[state[cur - 1]][cur - 1];
state[cur - 1] ^= 1;
cur = tmp;
}
nxt[state[cur - 1]][cur - 1] = ind;
state[cur - 1] ^= 1;
}
assert(*max_element(state.begin(), state.end()) == 0);
answer(c, nxt[0], nxt[1]);
}
