#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};
void create_circuit(int m, vi A) {
int n = sz(A);
int nsz = 0; while (POW2[nsz+1] <= n) nsz++;
vi C(m + 1, -1);
vi X(POW2[nsz+1]-1), Y(POW2[nsz+1]-1);
int cs = -1, cv = 1;
queue<pi> q;
q.push({cs--, 0});
while (!q.empty()) {
int cur = q.front().first, cur_depth = q.front().second;
cur = -cur - 1;
q.pop();
if (cur_depth >= nsz) {
X[cur] = cv++;
Y[cur] = cv++;
} else {
X[cur] = cs--;
Y[cur] = cs--;
}
if (X[cur] < 0) q.push({X[cur], cur_depth+1});
if (Y[cur] < 0) q.push({Y[cur], cur_depth+1});
}
vi order;
vi state(POW2[nsz+1]-1, 0);
int cur = -1;
while (order.size() < cv - 1) {
int rmcur = -cur - 1;
if (state[rmcur] == 0) {
cur = X[rmcur];
} else {
cur = Y[rmcur];
}
if (cur > 0) {
order.push_back(cur);
cur = -1;
}
state[rmcur] = 1 - state[rmcur];
}
vi to_change(POW2[nsz+1] + 1, -1);
if (n % 2 == 1) A.push_back(-1), n++;
int shift = 0; while (order[shift] != A[0] + 1) shift++;
int curi = 0;
for (int i = 0; i < n/2; i++) {
to_change[order[i]] = A[i];
to_change[order[i+shift]] = A[i+(n/2)];
}
to_change[order.back()] = 0;
for (int i = 0; i < POW2[nsz+1]-1; i++) {
if (X[i] > 0) X[i] = to_change[X[i]];
if (Y[i] > 0) Y[i] = to_change[Y[i]];
}
auto prune = [&](const auto &self, int v) {
if (X[v] == -1 && Y[v] == -1) {
return true;
}
if (X[v] < -1 && self(self, -X[v]-1)) X[v] = -1;
if (Y[v] < -1 && self(self, -Y[v]-1)) Y[v] = -1;
return X[v] == -1 && Y[v] == -1;
};
prune(prune, 0);
int cur_id = 0;
vi new_order, remapped(X.size());
auto rename = [&](const auto &self, int v) {
if (v >= 0) return;
else v = -v-1;
remapped[v] = -new_order.size()-1;
new_order.push_back(-v-1);
if (X[v] != -1)self(self, X[v]);
if (Y[v] != -1) self(self, Y[v]);
};
rename(rename, -1);
vi newX(new_order.size()), newY(new_order.size());
for (int i = 0; i < new_order.size(); i++) {
int old_id = new_order[i], old_name = -new_order[i]-1;
newX[i] = X[-old_id-1] >= 0 ? X[-old_id-1] : remapped[-X[-old_id-1]-1];
newY[i] = Y[-old_id-1] >= 0 ? Y[-old_id-1] : remapped[-Y[-old_id-1]-1];
}
X = newX;
Y = newY;
simulate(m, C, X, Y);
answer(C, X, Y);
}
