#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;
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) {
if (node < 0) node = -node - 1;
if (states[node]) {
states[node] = 0;
if (y[node] == MAX_N) {
y[node] = add;
return;
}
Add(y[node], add);
} else {
states[node] = 1;
if (x[node] == MAX_N) {
x[node] = add;
return;
}
Add(x[node], add);
}
}
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 = Create(bit);
for (int i = 0; i < n - 1; i++) {
Add(root, v[i]);
}
for (int i = n; i < 2 * a; i++) {
Add(root, -root - 1);
}
Add(root, v.back());
return root;
}
void create_circuit(int m, std::vector<int> a) {
int n = a.size();
a.push_back(0);
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);
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;
}
// } else if (graph[i].size() == 2) {
// x.push_back(graph[i][0]), y.push_back(graph[i][1]);
// c[i] = -int(x.size());
// } else if (graph[i].size() == 3) {
// int s1 = -int(x.size() + 1);
// int s2 = s1 - 1, s3 = s1 - 2;
// x.push_back(s2), y.push_back(s3); //s1
// x.push_back(graph[i][0]), y.push_back(s1); //s2
// x.push_back(graph[i][1]), y.push_back(graph[i][2]); //s3
// c[i] = s1;
// } else if (graph[i].size() == 4) {
// int s1 = -int(x.size() + 1);
// int s2 = s1 - 1, s3 = s1 - 2;
// x.push_back(s2), y.push_back(s3); //s1
// x.push_back(graph[i][0]), y.push_back(graph[i][2]); //s2
// x.push_back(graph[i][1]), y.push_back(graph[i][3]); //s3
// c[i] = s1;
// }
}
answer(c, x, y);
}
//5 14
//1 2 3 3 2 5 1 1 2 1 4 3 4 3
