#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int M, vector<int> A) {
int N = A.size();
A.push_back(M + 1);
vector<int> C(M + 1);
C[0] = A[0];
if (N == 1) {
C[A[0]] = 0;
answer(C, vector<int>(), vector<int>());
return;
}
int K = 0;
while ((1 << K) < N) {
K++;
}
vector<int> X;
vector<int> Y;
vector<int> cur_layer(1 << K, M + 1);
int cnt = 0;
for (int i = 0; i < (1 << K) - 1; i++) {
int last = 0;
for (int j = 0; j < K; j++) {
last |= ((i >> j) & 1) << (K - 1 - j);
}
if (last < ((1 << K) - N)) {
continue;
}
cur_layer[last] = A[++cnt];
}
cur_layer[(1 << K) - 1] = 0;
cnt = 0;
for (int i = K - 1; i >= 0; i--) {
vector<int> nxt_layer(1 << i, M + 1);
for (int j = 0; j < (1 << i); j++) {
if (cur_layer[j << 1] != M + 1 || cur_layer[j << 1 | 1] != M + 1) {
cnt++;
nxt_layer[j] = -cnt;
X.push_back(cur_layer[j << 1]);
Y.push_back(cur_layer[j << 1 | 1]);
}
}
cur_layer.swap(nxt_layer);
}
for (int i = 1; i <= M; i++) {
C[i] = cur_layer[0];
}
for (int i = 0; i < cnt; i++) {
if (X[i] == M + 1) {
X[i] = cur_layer[0];
}
if (Y[i] == M + 1) {
Y[i] = cur_layer[0];
}
}
answer(C, X, Y);
}
