#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
void create_circuit(int M, vector<int> A) {
int N = A.size();
A.push_back(0);
vector<int> C(M + 1);
vector<int> X, Y;
C[0] = A[0];
if (N == 1) {
C[A[0]] = 0;
} else {
for (int i = 1; i <= M; i++) {
C[i] = -1;
}
int L = N;
int b = 32 - __builtin_clz(L - 1);
int K = (1 << b);
vector<bool> rem(K + 1);
vector<pair<int, int>> swt(K + 1);
for (int i = 1, l = b - 1; l >= 0; l--, i = i + i + 1) {
if ((K - L) & (1 << l)) {
swt[i].first = -1;
int ll = i + i, rr = ll + 1;
for (int c = 0; c < l; c++, ll += ll, rr += rr) {
for (int j = ll; j < rr; j++) {
rem[j] = true;
swt[j].first = swt[j].second = -1;
}
}
}
}
int idx = 1;
vector<int> nid(K + 1);
for (int i = 1; i <= K; i++) {
if (!rem[i]) {
nid[i] = idx++;
}
}
vector<int> v;
for (int i = 0; i < K; i++) {
bitset<32> bs(i);
for (int j = 0; j < b / 2; j++) {
bool t = bs[j];
bs[j] = bs[b - j - 1];
bs[b - j - 1] = t;
}
v.push_back(bs.to_ulong());
}
for (int i = 0, k = K / 2; i < K; i += 2, k++) {
if (swt[k].first == -1) {
v[i] = INF;
}
if (swt[k].second == -1) {
v[i + 1] = INF;
}
}
vector<int> stv = v;
sort(stv.begin(), stv.end());
for (int i = 0; i < K; i++) {
if (v[i] != INF) {
v[i] = lower_bound(stv.begin(), stv.end(), v[i]) - stv.begin();
}
}
vector<int> xid, yid;
for (int i = 0, k = K / 2; k < K; i += 2, k++) {
if (swt[k].first != -1) {
xid.push_back(v[i]);
}
if (swt[k].second != -1) {
yid.push_back(v[i + 1]);
}
}
reverse(xid.begin(), xid.end());
reverse(yid.begin(), yid.end());
for (int i = 1; i < K / 2; i++) {
if (!rem[i]) {
if (swt[i].first != -1) {
X.push_back(-nid[i + i]);
} else {
X.push_back(-1);
}
if (swt[i].second != -1) {
Y.push_back(-nid[i + i + 1]);
} else {
Y.push_back(-1);
}
}
}
for (int i = K / 2; i < K; i++) {
if (!rem[i]) {
if (swt[i].first != -1) {
X.push_back(A[xid.back() + 1]);
xid.pop_back();
} else {
X.push_back(-1);
}
if (swt[i].second != -1) {
Y.push_back(A[yid.back() + 1]);
yid.pop_back();
} else {
Y.push_back(-1);
}
}
}
Y.back() = 0;
}
answer(C, X, Y);
}
