#include "doll.h"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
vector<int> C(M + 1, -1);
int lev = 0;
while ((1 << (lev + 1)) <= N) ++lev;
vector<int> X, Y;
while (lev >= 0) {
int n = 1 << lev;
if (n > N) {
X.push_back(-1);
Y.push_back(0);
--lev;
if (lev >= 0) Y.back() = -(int)X.size() - 1;
continue;
}
N -= n;
if (n == 1) {
X.push_back(1);
Y.push_back(0);
--lev;
}
else {
X.push_back(-(int)X.size() - 2);
Y.push_back(0);
int idx = Y.size() - 1;
int tmp = X.size();
rep2 (i, 1, n / 2) {
X.push_back(-(tmp + i * 2));
Y.push_back(-(tmp + i * 2 + 1));
}
rep2 (i, n / 2, n) {
X.push_back(1);
Y.push_back(1);
}
--lev;
Y[idx] = -(int)X.size() - 1;
}
}
{
int cur = 0;
int idx = 0;
vector<bool> sw(X.size(), true);
do {
if (cur >= 0) cur = C[cur];
else {
if (sw[-1 - cur]) {
sw[-1 - cur] = false;
if (X[-1 - cur] > 0) X[-1 - cur] = A[idx++];
cur = X[-1 - cur];
}
else {
sw[-1 - cur] = true;
if (Y[-1 - cur] > 0) Y[-1 - cur] = A[idx++];
cur = Y[-1 - cur];
}
}
} while (cur != 0);
}
answer(C, X, Y);
}
