#include "doll.h"
#include <bits/stdc++.h>
#define ll int
#define vll vector<ll>
#define pb push_back
#define sz size()
using namespace std;
void create_circuit(int m, std::vector<int> a) {
ll i;
ll n = a.size();
if(n==1){
vll c(m+1,0);
c[0]=a[0];
answer(c,{},{});
return;
}
vll c(m+1,-1);
c[0]=a[0];
a.erase(a.begin());
a.pb(0);
//~ for(auto i : a)cout<<i<<' ';
//~ cout<<endl;
ll bit=__lg(n);
if((1ll<<bit) < n)bit++;
vll x,y;
auto get = [&](){
x.pb(0);
y.pb(0);
return (ll)x.sz;
};
function<int(int,int,vector<int>)> build = [&](ll l,ll r,vll a){
if(a.size()==0)return -1;
if(l==r){
assert(a.size()==1);
return a[0];
}
ll m=(l+r)/2;
ll goLeft=max(0,(ll)a.size()-(r-m));
vll toL,toR;
for(i=0;i<goLeft;i++){
toL.pb(a[i]);
}
for(i=goLeft;i<(ll)a.size();i++){
toR.pb(a[i]);
}
ll root=get();
x[root-1]=build(l,m,toL);
y[root-1]=build(m+1,r,toR);
//~ cout<<-root<<' '<<x[root-1]<<' '<<y[root-1]<<endl;
return -root;
};
build(0,(1ll<<bit)-1,a);
vector<bool> f((ll)x.size()+5,0);
function<int(int, int)> simulate = [&](ll root,ll value){
if(root>=0) return value;
root=-root;
f[root-1]=!f[root-1];
if(f[root-1]){
x[root-1]=simulate(x[root-1],value);
}else{
y[root-1]=simulate(y[root-1],value);
}
return -root;
};
for(i=0;i<n;i++){
simulate(-1,a[i]);
}
answer(c, x, y);
}
