#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
const int INF=1e9;
struct sw{
int l=INF,r=INF;
int num;
bool flip=false;
};
int IDX=2;
sw sf[400005];
void simulate(int i){
int curr=-1;
while (true){
sf[-curr].flip^=true;
if (sf[-curr].flip){
if (sf[-curr].l==INF){
sf[-curr].l=i;
break;
}
curr=sf[-curr].l;
}
else{
if (sf[-curr].r==INF){
sf[-curr].r=i;
break;
}
curr=sf[-curr].r;
}
}
}
void create_circuit(int m, vector<int> arr) {
int n=sz(arr);
vector<int> dev={arr[0]};
rep(x,0,m) dev.push_back(-1);
if (sz(arr)==1){
dev[arr[0]]=0;
answer(dev,{0},{0});
return;
}
else if (sz(arr)==2){
answer(dev,{arr[1]},{0});
return;
}
arr.erase(arr.begin());
arr.push_back(0);
sf[1].num=sz(arr);
vector<int> layer={1};
int ss=1;
while (ss<sz(arr)) ss<<=1;
while (ss>>=1){
vector<int> temp;
for (auto &it:layer){
sw l,r;
r.num=min(ss,sf[it].num);
l.num=sf[it].num-r.num;
//cout<<l.num<<" "<<r.num<<endl;
if (l.num){
if (ss==1) continue;
temp.push_back(IDX);
sf[IDX]=l;
sf[it].l=-IDX;
IDX++;
}
else{
sf[it].l=-1;
}
if (ss==1) continue;
temp.push_back(IDX);
sf[IDX]=r;
sf[it].r=-IDX;
IDX++;
}
layer=temp;
}
rep(x,0,sz(arr)){
simulate(arr[x]);
}
//rep(x,1,IDX) cout<<sf[x].l<<" "; cout<<endl;
//rep(x,1,IDX) cout<<sf[x].r<<" "; cout<<endl;
vector<int> l,r;
rep(x,1,IDX) l.push_back(sf[x].l);
rep(x,1,IDX) r.push_back(sf[x].r);
answer(dev,l,r);
}
