#include "doll.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_M = 1e5 + 5;
const int MAX_N = 1e6;
vi graph[MAX_M];
int sz = 0, wait = 0;
vi x, y;
inline void Add() {
x.push_back(MAX_N), y.push_back(MAX_N);
sz++;
}
int Create(int d) {
int node = x.size();
Add();
if (d) {
int a = Create(d - 1);
x[node] = -a - 1;
a = Create(d - 1);
y[node] = -a - 1;
}
return node;
}
bitset<MAX_N> states;
void Add(int node, int add, int d) {
if (node < 0) node = -node - 1;
if (states[node]) {
states[node] = 0;
if (!d) {
y[node] = add;
wait--;
return;
}
if (y[node] == MAX_N) {
y[node] = -int(x.size()) - 1;
Add();
wait--;
}
Add(y[node], add, d - 1);
} else {
states[node] = 1;
if (!d) {
x[node] = add;
wait++;
return;
}
if (x[node] == MAX_N) {
x[node] = -int(x.size()) - 1;
Add();
wait++;
}
Add(x[node], add, d - 1);
}
}
void Add2(int node, int add, int d) {
if (node < 0) node = -node - 1;
if (states[node]) {
states[node] = 0;
if (y[node] == MAX_N) {
y[node] = add;
return;
}
Add2(y[node], add, d - 1);
} else {
states[node] = 1;
if (x[node] == MAX_N) {
x[node] = add;
return;
}
Add2(x[node], add, d - 1);
}
}
int Solve(vi &v) {
int n = v.size();
int bit = 0, a = 1;
for (a = 1; a < n; bit++, a <<= 1);
bit--;
a >>= 1;
int root = x.size();
Add();
for (int i = 0; i < n - 1; i++) {
Add(root, v[i], bit);
}
while (--wait) {
Add2(root, -root - 1, bit);
}
// for (int i = n; i < 2 * a; i++) {
// Add(root, -root - 1, bit);
// }
Add2(root, v.back(), bit);
return root;
}
void create_circuit(int m, std::vector<int> a) {
for (int i = 0; i <= m; i++) graph[i].clear();
x.clear(), y.clear();
int n = a.size();
a.push_back(0);
int t = a[0];
a.erase(a.begin());
if (a.size() == 1) {
vi c(m + 1, 0);
c[0] = t;
answer(c, x, y);
return;
}
// graph[0].push_back(a[0]);
// for (int i = 0; i < n; i++) {
// graph[a[i]].push_back(a[i + 1]);
// }
vi c(m + 1, -Solve(a) - 1);
c[0] = t;
// if (m == 1 && n != 1) {
// c[0] = 1, c[1] = -1;
// x.push_back(1), y.push_back(-2);
// for (int i = 1; i < n - 1; i++) {
// x.push_back(-i), y.push_back(-i - 2);
// }
// y.back() = 0;
// answer(c, x, y);
// return;
// }
// for (int i = 0; i <= m; i++) {
// if (graph[i].empty()) continue;
// if (graph[i].size() == 1) {
// c[i] = graph[i][0];
// } else {
// c[i] = -Solve(graph[i]) - 1;
// }
// }
answer(c, x, y);
}
//5 14
//1 2 3 3 2 5 1 1 2 1 4 3 4 3
//1 7
//1 1 1 1 1 1 1
