#include "doll.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
void create_circuit(int M, std::vector<int> A) {
int n = A.size();
vector<int> c(M+1, -1);
if(n == 1){
c[0] = A[0];
for(int i = 1; i<=M; i++){
c[i] = 0;
}
answer(c, {}, {});
return;
}
vector<int> x(2*n, INT_MAX); // da resizare
vector<int> y(2*n, INT_MAX);
int p2 = 1;
int h = 0;
while(p2<n){
p2 <<=1;
h++;
}
int dlt = p2-n;
int s= 1;
vector<pair<int, int*>> leaf;
auto build = [&](auto&& build, int curr, int md, int curr_h)->void{
int pow2 = (1<<curr_h);
int md1 = md;
int md2 = md+pow2;
pow2 <<= 1;
curr_h++;
if((1<<(h-curr_h)) <= dlt){
dlt -= (1<<(h-curr_h));
x[curr-1] = -1;
}
if(curr_h == h){
if(x[curr-1] != -1) leaf.push_back({md1, &x[curr-1]});
leaf.push_back({md2, &y[curr-1]});
}
else{
if(x[curr-1] != -1){
x[curr-1] = -(++s);
y[curr-1] = -(++s);
build(build, -x[curr-1], md1, curr_h);
build(build, -y[curr-1], md2, curr_h);
}
else{
y[curr-1] = -(++s);
build(build, -y[curr-1], md2, curr_h);
}
}
};
build(build, 1, 0, 0);
sort(leaf.begin(), leaf.end());
c[0] = A[0];
c[A[0]] = -1;
A.push_back(0);
for(int i = 0; i<n; i++){
*leaf[i].second = A[i+1];
if(i != n-1) c[A[i+1]] = -1;
}
while(x.back() == INT_MAX){
x.pop_back();
y.pop_back();
}
answer(c, x, y);
}
