#pragma GCC optimize("O3")
//#pragma GCC tagret("avx2")
#include<bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ld long double
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type,
less<ll>, rb_tree_tag,
tree_order_statistics_node_update> oset;
mt19937 gen(time(0));
const int MOD = 1e9 + 7;
void answer(vector<int> C, vector<int> X, vector<int> Y);
bool used[400007];
vector<int> X, Y;
ll build(ll gl) {
if(gl == 0) {
X.pb(0);
Y.pb(0);
return X.size() - 1;
}
ll v1 = X.size();
X.pb(-1);
Y.pb(-1);
X[v1] = -build(gl - 1);
Y[v1] = -build(gl - 1);
return v1;
}
void go(ll v1, ll l, ll r, ll cr, ll root) {
v1 = -v1;
if(l + 1 == r) {
if(l < cr) {
X[v1] = root;
}
if(r < cr) {
Y[v1] = root;
}
return;
}
ll mid = (l + r) / 2;
go(X[v1], l, mid, cr, root);
go(Y[v1], mid + 1, r, cr, root);
}
set<ll> recalc(ll v1, ll gl) {
v1 = -v1;
set<ll> st1, st2;
if(gl == 0) {
st1.insert(X[v1]);
st2.insert(Y[v1]);
} else {
for(auto to: recalc(X[v1], gl - 1)) st1.insert(to);
for(auto to: recalc(Y[v1], gl - 1)) st2.insert(to);
}
if(st1.size() == 1) {
X[v1] = *st1.begin();
}
if(st2.size() == 1) {
Y[v1] = *st2.begin();
}
for(auto to: st2) st1.insert(to);
while(st1.size() > 2) st1.erase(*st1.rbegin());
return st1;
}
bool col(ll v1, ll x, ll gl) {
v1 = -v1;
if(gl == 0) {
used[v1] ^= 1;
if(used[v1]) {
if(X[v1] != 0) return 0;
X[v1] = x;
} else {
if(Y[v1] != 0) return 0;
Y[v1] = x;
}
return 1;
}
bool f = 0;
if(!used[v1]) f = col(X[v1], x, gl - 1);
else f = col(Y[v1], x, gl - 1);
used[v1] ^= 1;
return f;
}
void dob(ll v1, ll x, ll gl) {
while(true) {
if(col(v1, x, gl)) break;
}
}
void create_circuit(int M, vector<int> B) {
//if(A.size() != 16) exit(-1);
X.clear();
Y.clear();
vector<ll> A;
for(int i = 1; i < B.size(); i++) {
A.pb(B[i]);
}
A.pb(0);
vector<int> sl(M + 1, 0);
X.pb(0);
Y.pb(0);
ll now = 0;
while((2 << now) < A.size()) {
now++;
}
ll root = -build(now);
for(auto &to: sl) to = root;
ll d = (2 << now) - A.size();
go(root, 0, (2 << now) - 1, d, root);
for(auto to: A) {
dob(root, to, now);
}
recalc(root, now);
sl[0] = B[0];
set<ll> all;
for(auto to: sl) {
if(to < 0) all.insert(-to);
}
for(int i = 1; i < X.size(); i++) {
if(X[i] < 0) all.insert(-X[i]);
if(Y[i] < 0) all.insert(-Y[i]);
}
map<ll,ll> mp;
ll e = -1;
for(auto to: all) {
mp[to] = e;
e--;
}
vector<int> x, y;
for(int i = 1; i < X.size(); i++) {
if(!all.count(i)) continue;
if(X[i] >= 0) x.pb(X[i]);
else
x.pb(mp[-X[i]]);
if(Y[i] >= 0) y.pb(Y[i]);
else
y.pb(mp[-Y[i]]);
}
for(auto &to: sl) {
if(to < 0) to = mp[-to];
}
answer(sl, x, y);
}
#ifdef LOCAL
int32_t main() {
}
#endif
