#include "bits/stdc++.h"
#include "doll.h"
using namespace std;
void create_circuit(int M, vector<int> A)
{
int N = A.size();
vector<int> C(M + 1);
C[0] = A[0];
vector<int> X, Y;
vector<vector<int>> g(M + 1);
for (int i = 0; i < N - 1; i++)
g[A[i]].push_back(A[i + 1]);
g[A.back()].push_back(0);
for (int i = 1; i <= M; i++)
{
int sz = g[i].size();
if (sz == 0)
continue;
if (sz == 1)
{
C[i] = g[i][0];
continue;
}
int x = 0;
while ((1ll << x) < sz)
x++;
int ind = X.size() + 1;
ind *= -1;
C[i] = ind;
int r = (1ll << x) - sz;
reverse(g[i].begin(), g[i].end());
while (sz < (1ll << x))
sz++, g[i].push_back(ind);
reverse(g[i].begin(), g[i].end());
vector<int> nw = g[i];
for (int j = 0; j < sz; j++)
{
int pos = 0;
int k = j;
for (int j = 0; j < x; j++)
if (k & (1ll << j))
pos += (1ll << (x - j - 1));
g[i][j] = nw[pos];
}
auto build = [&](auto build, int L, int R) -> void
{
if (R < r)
X.push_back(ind), Y.push_back(ind);
else if (L == R - 1)
X.push_back(g[i][L]), Y.push_back(g[i][R]);
else
{
int a = X.size() + 1;
X.push_back(ind);
Y.push_back(-a - 1);
int m = (L + R) / 2;
build(build, m + 1, R);
X[a - 1] = -(X.size() + 1);
build(build, L, m);
}
};
build(build, 0, sz - 1);
}
answer(C, X, Y);
}
