#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, int n){
if(n-(int)v.size() >= r)
return -1;
if(l+1 == r)
return v[l-n+(int)v.size()];
int m = (l+r)/2, x = add_switch();
set_child(x, build(v, l, m, n), build(v, m, r, n));
return -x-1;
}
void add(int x, vector<int> v){
int n = (int)v.size();
int log = 1;
while((1<<log) < n)
log++;
vector<int> inds(n);
iota(inds.begin(), inds.end(), (1<<log)-n);
sort(inds.begin(), inds.end(), [&log](int a, int b){ return get_reverse(a, log-1) < get_reverse(b, log-1); });
vector<int> v2(n);
for(int i = 0; i < n; i++)
v2[inds[i]-(1<<log)+n] = v[i];
build(v2, 0, 1<<log, 1<<log);
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 < (int)X.size(); i++)
//cout<<-i-1<<": "<<X[i]<<" "<<Y[i]<<"\n";
answer(C, X, Y);
}
