#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
ll LINF=(1LL<<61)-1;
ll MINF=1LL<<40;
int INF=INT_MAX>>1;
#include "doll.h"
template<class S>
void out_vector(vector<S> v){
for(S i:v)cerr<<i<<" ";
cerr<<"\n";
}
vector<int> X,Y;
int make(int x,int y){
if(y==0)return -1;
if(x==1)return 0;
X.emplace_back(0);
Y.emplace_back(0);
int ret=X.size();
int ri=make(x/2,min(y,x/2));
int lf=make(x/2,max(0,y-x/2));
X[ret-1]=lf;
Y[ret-1]=ri;
return -ret;
}
void create_circuit(int M, std::vector<int> A) {
int N=A.size();
A.emplace_back(0);
vector<int> C(M+1,-1);
C[0]=A[0];
int ceil=1;
while(ceil<N)ceil<<=1;
make(ceil,N);
if(N==1){
X={-1};
Y={0};
}
int S=X.size();
vector<int> cond(S,0);
vector<pair<int,int>> order;
rep(i,N){
int pos=-1;
while(true){
if(cond[-pos-1]==0){
cond[-pos-1]=1;
if(X[-pos-1]==0){
order.emplace_back(pos,0);
break;
}
else{
pos=X[-pos-1];
}
}
else{
cond[-pos-1]=0;
if(Y[-pos-1]==0){
order.emplace_back(pos,1);
break;
}
else{
pos=Y[-pos-1];
}
}
}
}
rep(i,N){
if(order[i].second==0){
X[-order[i].first-1]=A[i+1];
}
else{
Y[-order[i].first-1]=A[i+1];
}
}
answer(C,X,Y);
}
