#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void answer(vector<int> a, vector<int> b, vector<int> c);
void create_circuit(int M, vector<int> A) {
const int mn = 2e5 + 5;
vector<int> lg2(mn);
int cur = 1, ct = 0;
for (int i = 0; i < mn; i++) {
if (i > cur) {
cur *= 2;
ct++;
}
lg2[i] = ct;
}
int N = A.size();
vector<vector<int>> adj(M + 1);
adj[0].push_back(A[0]);
for (int i = 0; i + 1 < A.size(); i++) {
adj[A[i]].push_back(A[i + 1]);
}
adj[A.back()].push_back(0);
vector<int> c(M + 1), x, y;
vector<int> stat;
for (int i = 0; i <= M; i++) {
if (adj[i].empty()) {
c[i] = 0;
continue;
}
if (adj[i].size() == 1) {
c[i] = adj[i][0];
continue;
}
int num = adj[i].size();
int pow2 = (1 << lg2[num]);
function<int(int, int, int)> build = [&](int curin, int curl, int curr) {
if (curl >= num) {
return INT_MIN;
}
if (curl == curr) {
return INT_MAX;
}
int a = build(curin * 2 + 1, curl, (curl + curr) / 2),
b = build(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
x.push_back(b), y.push_back(a);
stat.push_back(0);
return -(int(x.size()));
};
c[i] = build(0, 0, pow2 - 1);
int in = 0;
function<void(int)> dfs = [&](int cur) {
if (cur >= 0)
return;
int tmp;
if (stat[-cur - 1] == 0) {
tmp = x[-cur - 1];
} else {
tmp = y[-cur - 1];
}
if (stat[-cur - 1] == 0) {
if (tmp == INT_MAX)
x[-cur - 1] = adj[i][in++];
else if (tmp == INT_MIN)
x[-cur - 1] = c[i];
else
dfs(tmp);
} else {
if (tmp == INT_MAX)
y[-cur - 1] = adj[i][in++];
else if (tmp == INT_MIN)
y[-cur - 1] = c[i];
else
dfs(tmp);
}
stat[-cur - 1] = 1 - stat[-cur - 1];
};
for (int j = 0; j < pow2; j++)
dfs(c[i]);
}
answer(c, x, y);
}
