#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
const ll inf = 1e8;
void create_circuit(int M, std::vector<int> A){
int N = A.size();
std::vector<int> C(M + 1, 0);
C[0] = A[0];
if (N == 1){
for (int i = 1; i <= M; ++i)
C[i] = 0;
vector<int> X, Y;
answer(C, X, Y);
return;
}
for (int i = 1; i <= M; ++i){
C[i] = -1;
}
ll GN = 1 << (__lg(N - 1) + 1);
A.push_back(0);
vector<int> X,Y;
ll it = 0;
function<ll(ll, ll,ll,ll)> dfs;
dfs = [&](ll cnt, ll width, ll st, ll lv){
//cerr << "dfs " << cnt << " " << width << " " << st << " " << lv << "\n";
if (width == 1){
return inf+st;
}
ll i = it++;
X.emplace_back();
Y.emplace_back();
if (width>=cnt*2){
X[i] = -1;
Y[i] = dfs(cnt,width/2,st+(1<<lv),lv+1);
}else{
ll leftsize = 1<<__lg(cnt-1);
X[i] = dfs(cnt-leftsize,leftsize,st,lv+1);
Y[i] = dfs(leftsize,leftsize,st+(1<<lv),lv+1);
}
return -1 - i;
};
dfs(N, GN,0,0);
//cerr << "S=" << X.size() << endl;
//for(ll i = 0;i<X.size();i++) cerr << X[i] << " \n"[i+1==X.size()];
//for(ll i = 0;i<Y.size();i++) cerr << Y[i] << " \n"[i+1==Y.size()];
vector<pair<ll,ll*>> v;
for(ll i = 0;i<X.size();i++) if (X[i]>=inf) v.push_back({X[i],&X[i]});
for(ll i = 0;i<Y.size();i++) if (Y[i]>=inf) v.push_back({Y[i],&Y[i]});
sort(v.begin(),v.end());
for(ll i = 0;i<N;i++){
*v[i].second = A[i+1];
}
answer(C, X, Y);
}
