#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 400005;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int k;
int n;
int msb(unsigned int n){
return 1<<(32-__builtin_clz(n));
}
int cur=-1;
int X[MAXN], Y[MAXN], C[MAXN];
bool state[MAXN];
int dnc(int st, int en){
int mi=(st+en)/2;
int idx=cur--;
if(st+1==en){
if(st>=n)X[-idx]=-1;
if(en>=n)Y[-idx]=-1;
return idx;
} else{
X[-idx]=dnc(st,mi);
Y[-idx]=dnc(mi+1,en);
return idx;
}
}
void trav(int x, int next){
if(state[-x]==0){
state[-x]=!state[-x];
if(X[-x]){
trav(X[-x],next);
} else{
X[-x]=next;
}
} else{
state[-x]=!state[-x];
if(Y[-x]){
trav(Y[-x],next);
} else{
Y[-x]=next;
}
}
}
void create_circuit(int M, vector<int> A) {
n=A.size();
if(n==0){
// do something.
exit(0);
}
k=msb(n);
dnc(0,k-1);
Y[-(cur+1)]=0;
C[0]=-1; // go to the first thing that i need to go
trav(-1,A[0]);
for(int i=0;i<n;i++){
C[A[i]]=-1;
if(i==n-1)trav(-1,0);
else trav(-1,A[i+1]);
}
vector<int> AA,AB,AC;
AA=vector<int>(M+1,-1);
int S=-cur;--S;
AB=vector<int>(S);AC=vector<int>(S);
for(int i=0;i<S;i++){
AB[i]=X[i+1];
AC[i]=Y[i+1];
}
answer(AA,AB,AC);
}
