#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()
typedef long long ll;
using vi = vector<int>;
using pi = pair<int, int>;
void simulate(int m, vi &C, vi &X, vi &Y) {
int cur = 0, done = 0;
vi state(X.size(), 0);
while (true) {
cout << cur << " ";
if (cur == 0 && done > 0) break;
if (cur >= 0) {
cur = C[cur];
} else {
state[(-cur) - 1] = 1 - state[(-cur) - 1];
if (state[(-cur) - 1] == 1) {
cur = X[(-cur) - 1];
} else {
cur = Y[(-cur) - 1];
}
}
done++;
}
cout << "\n";
}
const int POW2[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,524288};
vi X, Y, C;
int cur = 0;
int next_switch() {
X.resize(X.size() + 1);
Y.resize(Y.size() + 1);
cur--;
return -cur -1;
}
void create_circuit(int m, vi A) {
C.assign(m+1, -1);
int n = sz(A);
bool subbed = n % 2 == 0;
if (subbed) n--;
int L = 1; while ((L*2) <= n) L*=2;
vi nodes; int cur_pos = 1;
for (int i = 0; i < L; i++) {
int cc = next_switch();
X[cc] = cur_pos++;
Y[cc] = cur_pos++;
nodes.push_back(cur);
}
while (nodes.size() > 1) {
vi new_nodes;
while (nodes.size() > 1) {
int a = nodes.back(); nodes.pop_back();
int b = nodes.back(); nodes.pop_back();
int par = next_switch();
X[par] = a;
Y[par] = b;
new_nodes.push_back(cur);
}
if (nodes.size() == 1) {
new_nodes.push_back(nodes.back());
nodes.pop_back();
}
nodes = new_nodes;
}
int root = nodes[0];
// for (int i = 0; i < -cur; i++) {
// cout << (-i-1) << " " << X[i] << "\n";
// cout << (-i-1) << " " << Y[i] << "\n";
// }
vi order;
vi state(-cur+1, 0);
int cnode = root;
while(order.size() < cur_pos-1) {
int rcnode = -cnode - 1;
if (state[rcnode] == 0) {
cnode = X[rcnode];
} else {
cnode = Y[rcnode];
}
state[rcnode] = 1 - state[rcnode];
if (cnode > 0) {
order.push_back(cnode);
cnode = root;
}
}
vi to_swap(cur_pos, -1);
for (int i = 0; i < cur_pos - 1; i++) {
if (i < n) {
to_swap[order[i]] = A[subbed ? i + 1 : i];
} else if (i < cur_pos - 2) {
to_swap[order[i]] = root;
} else {
to_swap[order[i]] = 0;
}
}
for (int i = 0; i < -cur; i++) {
if (X[i] > 0) X[i] = to_swap[X[i]];
if (Y[i] > 0) Y[i] = to_swap[Y[i]];
}
C.assign(m+1, root);
if (subbed) C[0] = A[0];
// simulate(m,C, X, Y);
answer(C, X, Y);
}
