#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 500005
int t[4*N],L[N],R[N],sz,now;
bool sw[N];
vector<int> c,x,y,pos[N];
map<int,int> mp;
int bi(int x){
int i=1;
while(i<x)i<<=1;
return i;
}
int lbi(int x){
if(x==0)return 0;
return 1<<(31-__builtin_clz(x));
}
int bic(int x){
int i=1,cnt=0;
while(i<x)i<<=1,cnt++;
return cnt;
}
void cre(int x,int l,int r,int cnt){
if(l==r){t[x]=l>cnt;return ;}
int mid=(l+r)/2;
cre(x*2,l,mid,cnt);
cre(x*2+1,mid+1,r,cnt);
t[x]=t[x*2]+t[x*2+1];
}
void sol(int x,int l,int r){
mp[x];
if(l+1==r){
if(!t[x*2])L[x]=1;
return ;
}
int mid=(l+r)/2;
if(!t[x*2])L[x]=1;
else L[x]=x*2,sol(x*2,l,mid);
R[x]=x*2+1;
sol(x*2+1,mid+1,r);
}
void dfs(int s,vector<int> &a){
if(now>=a.size())return ;
if(!sw[s]){
sw[s]^=1;
if(!L[s]){
L[s]=-a[now++];
dfs(1,a);
}
else dfs(L[s],a);
}
else{
sw[s]^=1;
if(!R[s]){
R[s]=-a[now++];
dfs(1,a);
}
else dfs(R[s],a);
}
}
void create_circuit(int m,vector<int> a){
int n,i;
a.push_back(0);
n=a.size();
c.resize(m+1);
for(i=0;i<=m;i++)c[i]=-1;
cre(1,1,bi(n),bi(n)-n);
sol(1,1,bi(n));
dfs(1,a);
for(auto &[x,y]:mp)y=--sz;
for(auto [key,val]:mp){
if(L[key]>0)x.push_back(mp[L[key]]);
else x.push_back(-L[key]);
if(R[key]>0)y.push_back(mp[R[key]]);
else y.push_back(-R[key]);
}
answer(c,x,y);
}
