#include <bits/stdc++.h>
#define MAX 305000
void create_circuit(int M, std::vector<int> A);
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
bool tab[MAX*4];
std::vector<int> segue;
std::vector<int> con[MAX*4];
int indice[MAX];
int count=0;
int max=0;
int skip=0;
void gera_ordem(int l,int r,int pos=1){
if(l==r){
if(l<skip){indice[l]=-1;return;}
indice[l]=segue[count];
++count;
return;
}
int m = (l+r)/2;
if(!tab[pos]){
gera_ordem(l,m,pos*2);
}else gera_ordem(m+1,r,(pos*2)+1);
tab[pos]=!tab[pos];
}
int validos[MAX*4];
int gerando[MAX*4];
int valcurg[MAX*4];
int curg=1;
void build(int l,int r,int pos=1){
if(l==r)return;
int m =(l+r)/2;
max=std::max(max,pos);
// std::cout<<pos<<" "<<l<<" "<<r<<" "<<m<<"\n";
if(!validos[pos*2]){
con[pos].push_back(-1);
}else if(l!=m)
con[pos].push_back(-(gerando[pos*2]));
else con[pos].push_back(indice[l]);
if(!validos[(pos*2)+1]){
con[pos].push_back(-1);
}else if(r!=m+1)
con[pos].push_back(-(gerando[(pos*2)+1]));
else con[pos].push_back(indice[r]);
// std::cout<<indice[l]<<" "<<indice[r]<<"\n";
// std::cout<<"Forja "<< con[pos][0]<<" "<<con[pos][1]<<"\n";
build(l,m,pos*2);
build(m+1,r,(pos*2)+1);
}
void prepare_ground(int l,int r,int pos=1){
if(l==r){
if(indice[l]!=-1){
++validos[pos];
}
return;
}
int m =(l+r)/2;
prepare_ground(l,m,pos*2);
prepare_ground(m+1,r,(pos*2)+1);
validos[pos]=validos[pos*2]+validos[(pos*2)+1];
}
void prepare_ground2(int l,int r,int pos=1){
if(l==r){
return;
}
if(validos[pos]){
gerando[pos]=curg;
valcurg[curg]=pos;
++curg;
}
int m =(l+r)/2;
prepare_ground2(l,m,pos*2);
prepare_ground2(m+1,r,(pos*2)+1);
}
void create_circuit(int M, std::vector<int> A) {
if(A.size()==1){
std::vector<int> a,b,c;
a.push_back(A[0]);
for(int i=1;i!=M+1;++i){
a.push_back(0);
}
answer(a,b,c);
return;
}
int begin = A[0];
{
std::vector<int> novA;
for(int i=1;i!=A.size();++i)novA.push_back(A[i]);
A=novA;
}
int obj=0;
for(int i=1;;i*=2){
if(i>A.size()){
obj=i;break;
}
}
segue=A;
segue.push_back(0);
// obj=A.size()+(A.size()&1);
while(A.size()<obj-1){
A.push_back(-1);
++skip;
}
A.push_back(0);
int N = A.size();
for(int i=0;i!=N;++i){
gera_ordem(0,N-1);
}
// printf("ok\n");
prepare_ground(0,N-1);
prepare_ground2(0,N-1);
build(0,N-1);
for(int i=1;i<=max;++i){
// std::cout<<tab[i]<<" "<<i<<" estado!\n";
}
std::vector<int> emp;
for(int i=0;i!=M+1;++i)emp.push_back(-1);
emp[0]=begin;
std::vector<int> a,b;
// printf("bora\n");
for(int i=1;i<curg;++i){
// std::cout<<"Explora "<<i<<" "<<valcurg[i]<<"\n";
while(con[valcurg[i]].size()<2){
con[valcurg[i]].push_back(-1);
}
// std::cout<<con[i].size()<<" "<<i<<"!!\n";
a.push_back(con[valcurg[i]][0]);
b.push_back(con[valcurg[i]][1]);
//std::cout<<i<<" "<<con[i][0]<<"\n";
// std::cout<<i<<" "<<con[i][1]<<"\n";
}
// printf("resolvido\n");
answer(emp,a,b);
}
