#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(0);
vector<int> C(M + 1);
vector<int> X, Y;
vector<vector<int>> edge(M + 1);
for (int i = 0; i < N; i++) {
edge[A[i]].push_back(A[i + 1]);
}
C[0] = A[0];
for (int m = 1; m <= M; m++) {
if (edge[m].empty()) {}
else if (edge[m].size() == 1) {
C[m] = edge[m][0];
}
else {
int L = edge[m].size();
int b = 32 - __builtin_clz(L - 1);
int K = (1 << b);
C[m] = -X.size() - 1;
int xsz = X.size();
for (int i = 0; i < K / 2 - 1; i++) {
X.push_back(-xsz - (i + 1) * 2);
Y.push_back(-xsz - (i + 1) * 2 - 1);
}
for (int i = K / 2 - 1; i < K - 1; i++) {
X.push_back(C[m]);
Y.push_back(C[m]);
}
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());
}
vector<int> u(K);
for (int i = 0; i < K; i++) {
u[v[i]] = i;
}
for (int i = 0; i < K / 2; i++) {
X[xsz + K / 2 - 1 + u[i] / 2] = edge[m][i];
}
for (int i = K / 2; i < K; i++) {
if (i >= L - 1) {
Y[xsz + K / 2 - 1 + u[i] / 2] = -xsz - 1;
} else {
Y[xsz + K / 2 - 1 + u[i] / 2] = edge[m][i];
}
}
Y.back() = edge[m][L - 1];
}
}
answer(C, X, Y);
}
