#include "doll.h"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> X, Y;
vector<int> type;
int N, K;
int idx(int x){
return -x-1;
}
void dfs(int x, int y){
int k=y/2;
if(K-k >= N){
K-=k;
X[idx(x)]=-1;
}else{
if(k==1){
X[idx(x)]=0;
}
else{
X[idx(x)]=-((int)X.size()+1);
X.push_back(0); Y.push_back(0); type.push_back(0);
}
}
if(k==1){
Y[idx(x)]=0;
}else{
Y[idx(x)]=-((int)X.size()+1);
X.push_back(0); Y.push_back(0); type.push_back(0);
}
if(X[idx(x)]!=0 && X[idx(x)]!=-1) dfs(X[idx(x)], k);
if(Y[idx(x)]!=0 && Y[idx(x)]!=-1) dfs(Y[idx(x)], k);
}
void dfs2(int x, int y){
if(type[idx(x)]==0){
type[idx(x)]=1;
if(X[idx(x)]==0){
X[idx(x)]=y;
return;
}else{
dfs2(X[idx(x)], y);
return;
}
}else{
type[idx(x)]=0;
if(Y[idx(x)]==0){
Y[idx(x)]=y;
return;
}else{
dfs2(Y[idx(x)], y);
return;
}
}
}
void create_circuit(int M, vector<int> A) {
A.push_back(0);
N = (int)A.size();
int two=1; while(two<N) two*=2;
K = two;
if(N==1){
vector<int> C(M+1);
C[0]=A[0];
for(int i=1; i<=M; i++){
C[i]=0;
}
vector<int> XY(0);
answer(C, XY, XY);
return;
}
X.push_back(0); Y.push_back(0); type.push_back(0);
dfs(-1, two);
for(int i=0; i<N; i++){
dfs2(-1, A[i]);
}
vector<int> C(M+1);
for(int i=0; i<=M; i++){
C[i]=-1;
}
answer(C, X, Y);
return;
}
