#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
std::vector<int> X, Y;
int add_switch(){
X.push_back(0);
Y.push_back(0);
return (int)X.size()-1;
}
void set_child(int x, int l, int r){
X[x] = l;
Y[x] = r;
}
int get_reverse(int x, int log){
int ret = 0;
for(int i = log; i >= 0; i--)
if(x&(1<<i))
ret += (1<<(log-i));
return ret;
}
int build(vector<int> &v, int l, int r){
//cout<<l<<" "<<r<<"\n";
if(l+1 == r)
return v[l];
int m = (l+r)/2, x = add_switch();
set_child(x, build(v, l, m), build(v, m, r));
return -x-1;
}
void add(int x, vector<int> v){
int n = (int)v.size();
while(n != (n&(-n))) n += (n&(-n));
//cout<<n<<" asd"<<endl;
reverse(v.begin(), v.end());
v.resize(n, -(int)X.size()-1);
reverse(v.begin(), v.end());
vector<int> v2(n);
int log = 31 - __builtin_clz(n);
for(int i = 0; i < n; i++){
v2[get_reverse(i, log-1)] = v[i];
}
/*for(int x : v2)
cout<<x<<" ";
cout<<"\n";*/
build(v2, 0, n);
return;
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
std::vector<int> C(M + 1, -1);
A.push_back(0);
add(0, A);
/*for(int i = 0; i < X.size(); i++)
cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<"\n";
cout<<"C\n";
for(int x : C)
cout<<x<<"\n";*/
answer(C, X, Y);
}
