#include "doll.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int cnt[200006];
bool sw[400006];
int n, s;
vector<int> c, a, b;
bool goForward(int &x) {
if (x >= 0) {
if (c[x] == -2e9) return false;
x = c[x];
} else {
if (!sw[-x - 1]) {
if (a[-x - 1] == -2e9) return false;
sw[-x - 1] = true;
x = a[-x - 1];
} else {
if (b[-x - 1] == -2e9) return false;
sw[-x - 1] = false;
x = b[-x - 1];
}
}
return true;
}
void create_circuit(int m, vector<int> A) {
n = (int)A.size();
c.resize(m + 1);
for (int i = 0; i < n; i++) cnt[A[i] - 1]++;
for (int i = 0; i < m + 1; i++) c[i] = -2e9;
for (int i = 0; i < m; i++) if (cnt[i]) {
int bit = ceil(log2(cnt[i]));
int sw_size = 1 << bit;
int left = sw_size - cnt[i];
vector<pair<int, int>> sw_cnt, nsw_cnt;
sw_cnt.push_back({ i + 1, -1 });
int st_s = -1;
for (int t = bit - 1; t >= 0; t--) {
bool rem = false;
if (left >= 1 << t) {
left -= 1 << t;
rem = true;
}
nsw_cnt.clear();
for (int i = 0; i < (int)sw_cnt.size(); i++) {
if (sw_cnt[i].second == -1) c[sw_cnt[i].first] = -s - 1;
else if (sw_cnt[i].second == 0) a[sw_cnt[i].first] = -s - 1;
else b[sw_cnt[i].first] = -s - 1;
if (rem) {
nsw_cnt.push_back({ s, 1 });
a.push_back(-st_s - 1);
b.push_back(-2e9);
rem = false;
} else {
nsw_cnt.push_back({ s, 0 });
nsw_cnt.push_back({ s, 1 });
a.push_back(-2e9);
b.push_back(-2e9);
}
if (st_s == -1) st_s = s;
s++;
}
sw_cnt = nsw_cnt;
}
}
A.push_back(0);
int curr = 0;
for (int i = 0; i <= n; i++) {
while (goForward(curr)) ;
if (curr >= 0) c[curr] = A[i];
else if (!sw[-curr - 1]) {
a[-curr - 1] = A[i];
sw[-curr - 1] = true;
} else {
b[-curr - 1] = A[i];
sw[-curr - 1] = false;
}
curr = A[i];
}
for (int i = 0; i <= m; i++) if (c[i] == -2e9) c[i] = 0;
answer(c, a, b);
}
