#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
/*struct nod {
int nr;
int x, y;
bool u;
};
nod h[600010];
node *H;
void build(int n, vector<int> A) {
A.push_back(0);//!!!
int k=0, leaves = (1<<(ceil(log2(n))))-1;
while (k<=leaves) {
if (k > leaves/2) {
h[++k] = {k, 1, 1, false};
} else {
h[++k]={k, 2*k, 2*k+1, false}
}
}
k=0;
while (k<=n) {
int p=1
if (!h[p].u) {
p=2*n;
if (p>leaves) {
h[p/2].x = A[k];
}
} else {
p=2*n+1;
if (p>leaves) {
h[p/2].y = A[k];
}
}
}
int k = 1, leaves = (1<<(ceil(log2(n)))-1);
H = new node(k, 0, 0);
node p = H;
while (k <= leaves) {
if (k >= leaves/2) {
p.x = p.y = H;
} else {
p.x = new no
}
}
}
void build(int nr, int h, node *p) {
if (h== htree) {
p.x = p.y = H;
return;
}
p.x = new node(nr*2, 0,0,0,0);
build(2*nr, h+1, p.x);
p.y = new node(nr*2+1, 0,0,0,0);
build(2*nr+1, h+1, p.x);
}*/
int height;
struct node {
int nr;
bool u;
node *x;
node *y;
};
node *H;
std::vector<int> X(400005), Y(400005);
void build(int nr, int h, node* p) {
//cout<<"!"<<p->nr<<'\n';
if (h == height) {
p->x = p->y = H;
//cout<<"!"<<p->nr<<"\n";
return;
}
X[p->nr -1] = -2*nr;
Y[p->nr -1] = -(2*nr+1);
p->x = new node({2*nr, 0, 0, 0});
build(2*nr, h+1, p->x);
p->y = new node({2*nr + 1, 0, 0, 0});
build(2*nr + 1, h+1, p->y);
}
void create_circuit(int M, std::vector<int> A) {
A.push_back(0);
std::vector<int> C(M + 1);
height = ceil(log2(A.size()));
//cout<<height<<'\n';
int leaves = (1<< (int)(ceil(log2(A.size())))) - 1;
//cout<<"Leaves = "<<leaves<<'\n';
H = new node({1,0,0,0});
build(1, 1, H);
int k=0; //insert 0 in a
while (k<A.size()) { //check
// cout<<"k="<<k<<'\n';
node* p=H;
while (p->y != H) { //switch u before if
p->u = !(p->u);
if ((p->u)) {
p=p->x;
} else {
p=p->y;
}
// cout<<p->nr<<'.';
}
if (!(p->u)) {
p->x = new node({A[k], 0,0,0});
X[p->nr -1]=A[k];
++k;
} else {
p->y = new node({A[k],0,0,0});
Y[p->nr -1]=A[k];
++k;
}
p->u = !(p->u);
}
//cout<<"!!!!!!K"<<k<<'\n';
for (int i=0; i<=M+1; i++) C[i]=-1;
X.resize(leaves); // x-1
Y.resize(leaves);
for (int i=0; i<X.size(); i++) {
if (X[i]==0) X[i]=-1;
if (Y[i]==0 && i!=X.size()-1) Y[i]=-1;
//cout<<X[i]<<" "<<Y[i]<<'\n';
}
answer(C, X, Y);
}
