#include "doll.h"
#include <bits/stdc++.h>
void create_circuit(int M, std::vector<int> A) {
int N = (int)A.size();
++N;
A.push_back(0);
// i -> 2 * i, 2 * i + 1
int logn = 1;
while ((1 << logn) < N) ++logn;
const int s = 1 << logn;
std::vector<bool> isUse(2 * s);
auto dfs = [&](auto &&self, const int i) -> bool {
if (i >= s) {
return isUse[i] = (s - (i - s) - 1) < N;
} else {
const auto a = self(self, 2 * i), b = self(self, 2 * i + 1);
return isUse[i] = a or b;
}
};
dfs(dfs, 1);
std::vector<int> ids;
for (int i = 1; i < 2 * s; ++i) {
if (isUse[i]) {
ids.push_back(i);
}
}
std::vector<int> X(s, -1), Y(s, -1);
for (int i = 1; i < s; ++i) {
if (isUse[i]) {
X[i] = 2 * i;
Y[i] = 2 * i + 1;
auto itr = std::lower_bound(ids.begin(), ids.end(), X[i]);
if (itr != ids.end() and *itr == X[i]) {
X[i] = itr - ids.begin();
} else {
X[i] = 0;
}
itr = std::lower_bound(ids.begin(), ids.end(), Y[i]);
if (itr != ids.end() and *itr == Y[i]) {
Y[i] = itr - ids.begin();
} else {
Y[i] = 0;
}
}
}
{
std::vector<int> x, y;
for (int i = 1; i < s; ++i) {
if (std::max(X[i], Y[i]) != -1) {
x.push_back(X[i]);
y.push_back(Y[i]);
}
}
X = x;
Y = y;
}
const int E = (int)X.size();
std::vector<bool> state(E, true);
std::vector<int> C(M + 1, -1);
for (int j = 0; j < N; ++j) {
int i = 0, p = -1;
while (ids[i] < s) {
const int nxt = state[i] ? X[i] : Y[i];
state[i] = not state[i];
p = i;
i = nxt;
}
(state[p] ? Y[p] : X[p]) = -A[j] - 1;
}
for (int i = 0; i < E; ++i) {
++X[i];
X[i] *= -1;
++Y[i];
Y[i] *= -1;
}
answer(C, X, Y);
}
