#include <bits/extc++.h>
#include "doll.h"
namespace {
template <class T> using Vec = std::vector<T>;
template <class T, class U> using HashTable = __gnu_pbds::gp_hash_table<T, U>;
int get_id() {
static int id = 0;
id -= 1;
return id;
}
}
void create_circuit(int M, Vec<int> A) {
A.push_back(0);
const int N = (int) A.size();
HashTable<int, Vec<int>> graph;
for (int i = 1; i <= M; ++i) {
graph[i].push_back(-1);
}
{
int H = 0;
while ((1 << H) < N) {
H += 1;
}
int M = N, last = 0;
while ((1 << H) != M) {
const int S = 1 << (H - 1);
M -= S;
Vec<int> id(S);
for (int i = 0; i < S; ++i) {
id[i] = get_id();
}
graph[last].push_back(id[0]);
last = id[0];
graph[last].push_back(id[1]);
for (int i = S / 2 - 1; i > 0; --i) {
graph[id[i]].push_back(id[2 * i]);
graph[id[i]].push_back(id[2 * i + 1]);
}
H -= 1;
const int root = last;
while ((1 << (H - 1)) >= M) {
const int u = get_id();
graph[last].push_back(u);
graph[u].push_back(root);
last = u;
H -= 1;
}
}
if (M > 1) {
int S = M;
Vec<int> id(M);
for (int i = 1; i < S; ++i) {
id[i] = get_id();
}
graph[last].push_back(id[1]);
for (int i = S / 2 - 1; i > 0; --i) {
graph[id[i]].push_back(id[2 * i]);
graph[id[i]].push_back(id[2 * i + 1]);
}
}
}
HashTable<int, int> idx;
for (int i = 0; i < N; ++i) {
int x = -1;
while (true) {
idx[x] ^= 1;
if ((int) graph[x].size() <= (idx[x] ^ 1)) {
break;
}
x = graph[x][idx[x] ^ 1];
}
graph[x].push_back(A[i]);
}
const int S = -(get_id() + 1);
Vec<int> C(M + 1), X(S), Y(S);
for (const auto [i, g] : graph) {
if (i >= 0) {
C[i] = g[0];
} else {
X[-(i + 1)] = g[0];
Y[-(i + 1)] = g[1];
}
}
answer(C, X, Y);
}
