#include "doll.h"
#include <iostream>
using namespace std;
vector<int> X, Y;
vector<int> XX, YY;
vector<int> was;
int S;
void rec(int pos, int val) {
if (was[pos] == 0) {
if (XX[pos] == 0) {
X[pos] = val;
XX[pos] = 1;
was[pos] ^= 1;
return;
}
else {
was[pos] ^= 1;
rec(-X[pos] - 1, val);
}
}
else {
if (YY[pos] == 0) {
YY[pos] = 1;
Y[pos] = val;
was[pos] ^= 1;
return;
}
else {
was[pos] ^= 1;
rec(-Y[pos] - 1, val);
}
}
}
void build(int v, int cur, int len) {
if (cur < len) {
XX[v] = 1;
YY[v] = 1;
S++;
X[v] = -S;
was.push_back(0);
X.push_back(0), Y.push_back(0);
XX.push_back(0), YY.push_back(0);
S++;
Y[v] = -S;
was.push_back(0);
X.push_back(0), Y.push_back(0);
XX.push_back(0), YY.push_back(0);
build(-X[v] - 1, cur + 1, len);
build(-Y[v] - 1, cur + 1, len);
}
else {
return;
}
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
vector<int> C(M + 1);
X.clear(), Y.clear();
A.push_back(0);
C[0] = A[0];
int n = 1, len = 0;
while (n < N)
n <<= 1, len++;
N++;
S++;
was.push_back(0);
X.push_back(0), Y.push_back(0);
XX.push_back(0), YY.push_back(0);
for (int i = 1; i <= M; ++i)
C[i] = -S;
build(0, 1, len);
for (int i = 1; i < N - 1; ++i)
rec(0, A[i]);
for (int i = N - 2; i < n - 1; ++i)
rec(0, -1);
rec(0, A[N - 1]);
answer(C, X, Y);
}
