#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define LOO(i,a,b) for (int i = a; i <=b;i++)
#define pii pair<int,int>
#define PB push_back
#define F first
typedef long long ll;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int curr = 0;
int getbigg(int n) {
int num = 1 << (31 - __builtin_clz(n));
if (num==n) return n;
return 1 << (32 - __builtin_clz(n));
}
int maxydep = 0;
vector<pii> outgoers;
vector<vector<int>> depths(30);
bool build(int v, int l, int r, int m, int rii, int depth) {
if (l==r) {
if (l==0 || rii==r) {
return true;
}
return false;
}
int mid = (l+r)/2;
pii mhm = {-1,-1};
if (build(2*v, l, mid, m, rii,depth+1)) {
mhm.F = curr;
}
if (build(2*v+1, mid+1,r,m,rii,depth+1)) {
mhm.second = curr;
}
if (mhm!=make_pair(-1,-1)) {
maxydep = max(maxydep, depth);
curr++;
if (l+1==r) mhm = {-1,-1};
if (mhm.F==-1||mhm.second==-1) {
depths[depth].PB(curr);
}
outgoers.PB(mhm);
return true;
}
return false;
}vector<bool> swpp;
vector<int> answ;
vector<int> gg;
int toppy;
bool traver(int smth, int l, int r) {
int current = toppy;
while (true) {
if (swpp[current]) {
swpp[current]=!swpp[current];
if (outgoers[current].F==toppy) return false;
if (l+1!=r) {
r = (l+r)/2;
current = outgoers[current].F;
}
else {
outgoers[current].F = -gg[smth];
return true;
}
}
else {
swpp[current]=!swpp[current];
if (outgoers[current].second==toppy) return false;
if (l+1!=r) {
current = outgoers[current].second;
l = (l+r)/2+1;
}
else {
outgoers[current].second = -gg[smth];
return true;
}
}
}
}
void create_circuit(int m, std::vector<int> a) {
if (a.size()==1) {
answer({a[0], 0}, {}, {});
return;
}
gg = a;
gg.PB(0);
int n = a.size();
outgoers.PB({0,0});
int upper2 = getbigg(n+1);
build(1, 0, upper2-1, n-1, upper2-1,0);
int progry = 0;
toppy = curr;
while (progry!=gg.size()) {
for (int i = 29; i>=0;i--) {
if (!depths[i].empty()) {
if (i==maxydep) {
progry++;
if (outgoers[depths[i].back()].F==-1) {
outgoers[depths[i].back()].F = depths[i].back();
}
else if (outgoers[depths[i].back()].second==-1) {
outgoers[depths[i].back()].second = depths[i].back();
}
if (outgoers[depths[i].back()].F!=-1 && outgoers[depths[i].back()].second!=-1) {
depths[i].pop_back();
}
break;
}
if (outgoers[depths[i].back()].F==-1) {
curr++;
outgoers[depths[i].back()].F=curr;
depths[i+1].push_back(curr);
outgoers.PB({-1,-1});
}
else if (outgoers[depths[i].back()].second==-1) {
curr++;
outgoers[depths[i].back()].second=curr;
depths[i+1].push_back(curr);
outgoers.PB({-1,-1});
}
if (outgoers[depths[i].back()].F!=-1 && outgoers[depths[i].back()].second!=-1) {
depths[i].pop_back();
}
break;
}
}
}
for (auto &ele: outgoers) {
if (ele.F==-1) ele.F=toppy;
if (ele.second==-1) ele.second=toppy;
}
vector C(m+1, -toppy);
swpp.assign(outgoers.size(), true);
answ.assign(upper2, -1);
int current = 0;
LOO(i,0, upper2-1) {
if (traver(current, 0, upper2-1)) {
current++;
}
}
vector<int> X((int)outgoers.size()-1), Y((int)(outgoers.size())-1);
LOO(i,1,outgoers.size()-1) {
X[i-1] = -outgoers[i].F;
Y[i-1] = -outgoers[i].second;
}
answer(C, X, Y);
}
