#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+10;
int tree[MAXN*4];
int cal[MAXN*4];
int id[MAXN*4];
void create_circuit(int M, std::vector<int> A) {
int n = (int)A.size();
vector<int> C;
vector<int> X;
vector<int> Y;
C = vector<int> (M+1);
if(n==1){
C[0] = A[0];
answer(C,X,Y);
return;
}
int base = 1;
for(;base<n;base<<=1);
for(int i=base-1;i>=base-n;i--){
tree[i+base] = 1;
}
for(int i=base-1;i>=1;i--){
tree[i] = tree[(i<<1)]|tree[(i<<1)|1];
}
vector<int> ord;
int cur = 1;
for(int i=0;i<base;i++){
cur = 1;
while(cur<base){
if(cal[cur]){
cal[cur] = 0;
cur<<=1;
cur|=1;
}
else {
cal[cur] = 1;
cur<<=1;
}
}
if(tree[cur]){
ord.push_back(cur-base);
}
}
assert((int)ord.size()==n);
int cnt = 0;
for(int i=1;i<base;i++){
if(tree[i]){
cnt++;
id[i] = -cnt;
}
}
for(int i=0;i<n;i++){
if(i==n-1)id[ord[i]+base] = 0;
else id[ord[i]+base] = A[i+1];
}
C[0] = A[0];
for(int i=1;i<=M;i++){
C[i] = -1;
}
X = vector<int> (cnt);
Y = vector<int> (cnt);
int cidx = 0;
for(int i=1;i<base;i++){
if(tree[i]){
if(tree[(i<<1)]){
X[cidx] = id[(i<<1)];
}
else {
X[cidx] = -1;
}
if(tree[(i<<1)|1]){
Y[cidx] = id[(i<<1)|1];
}
else {
Y[cidx] = -1;
}
cidx++;
}
}
answer(C,X,Y);
return;
}
