#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 42;
int id = 0, n;
vector<int> nxt[2], state;
int tree(int lvl, int deb) {
if(deb >= n) return -INF;
if(lvl == 0) return 0;
lvl--;
int mid = deb + (1 << (lvl));
int right = tree(lvl, deb), left = tree(lvl, mid);
nxt[0].push_back(left);
nxt[1].push_back(right);
return --id;
}
void create_circuit(int M, vector<int> A) {
A.push_back(0);
n = (int)A.size();
vector<int> C(M + 1);
if(n == 2) {
C[0] = 1, C[1] = 0;
answer(C, nxt[0], nxt[1]);
return;
}
int len = 0;
while((1 << len) <= n) len++;
tree(len, 0);
int sz = (int)nxt[0].size();
for (int i = 0; i <= M; ++i)
C[i] = -sz;
for(int i = 0; i < sz; i++) {
if(nxt[0][i] == -INF)
nxt[0][i] = -sz;
if(nxt[1][i] == -INF)
nxt[1][i] = -sz;
}
state.resize((int)nxt[0].size());
id = 0;
int i = sz-1;
while(i != -1) {
int nex = -nxt[state[i]][i]-1;
if(nxt[state[i]][i] == 0) {
nxt[state[i]][i] = A[id++];
nex = sz-1;
if(nxt[state[i]][i] == 0) nex = -1;
}
state[i] = 1 - state[i];
i = nex;
}
answer(C, nxt[0], nxt[1]);
}
