#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
int liscie[1000010];
map<int, int>mapa;
bool czy[1000010];
void create_circuit(int m, std::vector<int> A) {
A.push_back(0);
int n = A.size(), i;
int base = 1;
int log = 1;
while(base<n){
base*=2;
log++;
}
vector<int>pozycje;
for(i=0;i<base;i++){
int x = i;
int res = 0;
int pom = base/2;
while(x>0){
if(x%2)res+=pom;
pom/=2;
x/=2;
}
if(res>=base-n)
pozycje.push_back(res);
}
for(i=0;i<base;i++)liscie[i] = -1;
for(i=0;i<n;i++){
liscie[pozycje[i]] = A[i];
}
//for(auto j: pozycje)printf("%d ", j);printf("\n");
vector<int>C(m+1, -1);
vector<int>X,Y;
for(i=1;i<base;i++){
mapa[i] = i;
if(i*2<base){
X.push_back(-(i*2));
Y.push_back(-(i*2+1));
}
else{
X.push_back(liscie[i*2-base]);
Y.push_back(liscie[i*2+1-base]);
}
}
//answer(C, X, Y);return;
// for(i=0;i<base;i++)printf("%d ", liscie[i]);
for(i=base-1;i>=1;i--){
if(i*2>=base)
czy[i] = (liscie[i*2+1-base]!=-1);
else
czy[i] = czy[i*2]|czy[i*2+1];
if(!czy[i]){
mapa.erase(i);
}
}
// for(i=1;i<base;i++)printf("%d\n", czy[i]);
int it=1;
for(auto &j: mapa){
j.second = it++;
// printf("%d %d\n", j.first, j.second);
}
vector<int>X1, Y1;
for(int i=1;i<base;i++){
if(mapa.find(i)!=mapa.end()){
if(i*2>=base){
X1.push_back(X[i-1]);
Y1.push_back(Y[i-1]);
continue;
}
if(czy[i*2])
X1.push_back(-mapa[-X[i-1]]);
else
X1.push_back(-1);
if(czy[i*2+1])
Y1.push_back(-mapa[-Y[i-1]]);
else
Y1.push_back(-1);
}
}
// for(auto j: X1)printf("%d ", j);printf("\n");
// for(auto j: Y1)printf("%d ", j);printf("\n");
answer(C, X1, Y1);
}
