#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
struct sw {
int nxt[2];
int flag = 0;
bool end = false;
};
vector<sw> switches;
int cnt = 0;
void walk(int cur, int trig) {
if (switches[cur].end) {
if (cnt == 1 && trig == -1) {
switches[cur].nxt[switches[cur].flag] = 0;
switches[cur].flag = 1-switches[cur].flag;
return;
}
switches[cur].nxt[switches[cur].flag] = trig;
switches[cur].flag = 1-switches[cur].flag;
cnt--;
return;
}
walk(switches[cur].nxt[switches[cur].flag], trig);
switches[cur].flag = 1-switches[cur].flag;
}
void create_circuit(int M, vector<int> A) {
int n = A.size();
int sz = 1;
while (sz < n) sz *= 2;
switches.resize(sz);
for (int i = 1; 2*i < sz; i++) {
switches[i].nxt[0] = 2*i;
switches[i].nxt[1] = 2*i+1;
}
for (int i = sz/2; i < sz; i++) {
switches[i].end = true;
cnt += 2;
}
for (int i = 1; i < n; i++)
walk(1, A[i]);
while (cnt > 1) walk(1, -1);
vector<int> c(M+1, -1), x(sz-1), y(sz-1);
c[0] = A[0];
for (int i = 1; i < sz; i++) {
if (!switches[i].end) {
x[i-1] = -switches[i].nxt[0];
y[i-1] = -switches[i].nxt[1];
}
else {
x[i-1] = switches[i].nxt[0];
y[i-1] = switches[i].nxt[1];
}
}
answer(c, x, y);
return;
}
