#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);
vi count(m+1, 0);
vector<vi> nxt(m+1, vi());
for (int i = 0; i < n; i++) {
count[A[i]]++;
if (i != n - 1) nxt[A[i]].push_back(A[i+1]);
else nxt[A[i]].push_back(0);
}
C[0] = A[0];
vi owner(m+1, 0);
for (int i = 1; i <= m; i++) {
if (count[i] <= 0) continue;
owner[i] = -next_switch()-1;
}
for (int i = 1; i <= m; i++) {
if (count[i] <= 0) continue;
C[i] = owner[i];
int a = -owner[i]-1;
int b = 0, c = 0;
if (count[i] >= 3) {
b = next_switch();
c = next_switch();
X[a] = -b-1;
Y[a] = -c-1;
}
if (count[i] == 1) {
X[a] = -a-1;
Y[a] = nxt[i][0];
} else if (count[i] == 2) {
X[a] = nxt[i][0];
Y[a] = nxt[i][1];
} else if (count[i] == 3) {
X[b] = nxt[i][0];
Y[b] = nxt[i][1];
X[c] = -a-1;
Y[c] = nxt[i][2];
} else if (count[i] == 4) {
X[b] = nxt[i][0];
Y[b] = nxt[i][2];
X[c] = nxt[i][1];
Y[c] = nxt[i][3];
}
}
simulate(m, C, X, Y);
answer(C, X, Y);
// 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);
}
