#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int build(int qnt, int &extra, vector<int> &X, vector<int> &Y)
{
if (qnt == 1) return 0;
X.push_back(-1); Y.push_back(-1);
int id = X.size();
if (qnt <= extra)
{
extra -= qnt;
return -id;
}
int e = build(qnt/2, extra, X, Y), d = build(qnt/2, extra, X, Y);
X[id-1] = e, Y[id-1] = d;
return -id;
}
void create_circuit(int M, std::vector<int> A)
{
int N = A.size();
if (N == 1)
{
vector<int> C = {A[0], 0};
vector<int> X, Y;
answer(C, X, Y);
return;
}
vector<int> X, Y;
int qnt = 1;
while (qnt < N) qnt *= 2;
int extra = qnt - N;
bool delay = 0;
if (extra % 2) extra--, delay = 1;
build(qnt, extra, X, Y);
vector<int> C(M+1, -1); C[0] = (delay ? -1 : A[0]);
vector<int> state(X.size());
for (int i = 1-(int)delay; i < N; i++)
{
int id = -1;
while (id < 0)
{
int nextId = (state[-id-1] ? Y[-id-1] : X[-id-1]);
state[-id-1] ^= 1;
if (nextId == 0)
{
if (state[-id-1]) X[-id-1] = A[i];
else Y[-id-1] = A[i];
break;
}
id = nextId;
}
}
answer(C, X, Y);
}
