#include "doll.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int>ans1,ans2,c,arr;
int n,m,now=0,vis[400015];
pii seg[400015];
int build(int l,int r,int root,int out){
if (l==r)
return -root;
int mid=(l+r)>>1,use=--now;
use=abs(use);
if (out<(mid-l+1)){
seg[use].x=build(l,mid,root,out);
seg[use].y=build(mid+1,r,root,0);
}
else {
out-=(mid-l+1);
seg[use].x=root;
seg[use].y=build(mid+1,r,root,out);
}
return use;
}
void dfs(int i,int order,int root){
if (order==arr.size()) return;
if (!vis[i]){
vis[i]^=1;
if (seg[i].x==-root)
ans1[i]=arr[order++];
else ans1[i]=-seg[i].x;
dfs(abs(seg[i].x),order,root);
}
else {
vis[i]^=1;
if (seg[i].y==-root)
ans2[i]=arr[order++];
else ans2[i]=-seg[i].y;
dfs(abs(seg[i].y),order,root);
}
return;
}
void create_circuit(int M, std::vector<int> A) {
m=M;
ans1.resize(400000); ans2.resize(400000);
A.push_back(0);
n = A.size(); arr=A;
c.resize(m+1,-1);
int p=__lg(n-1)+1;
build(0,(1LL<<p)-1,1,(1LL<<p)-n);
dfs(1,0,1);
now=abs(now);
vector<int>X,Y;
for (int i=1;i<=now;i++){
X.push_back(ans1[i]);
}
for (int i=1;i<=now;i++){
Y.push_back(ans2[i]);
}
answer(c, X, Y);
}
/*
2 16
1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 2 1
4 7
1 1 1 1 1 1 1 1
./rand
./doll
*/
