#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int v[400010] , elem , newp[400010] , leaf , f[400010] , exists[400010];
pair < int , int > order[400010];
vector <int> w[400010] , x , y;
void dfs (int nod , int conf , int p2 , int val , int linit , int dif){
exists[nod] = 1;
if (2 * nod > val){ /// ar trb sa unesti cu ceva din a sau cu -1
order[++leaf] = make_pair(conf , nod);
order[++leaf] = make_pair(conf + (1 << p2) , nod);
return;
}
else {
if (((1 << (linit - p2 - 1)) & dif) && !f[linit - p2 - 1]){
f[linit - p2 - 1] = 1;
w[nod].push_back(1);
w[nod].push_back(2 * nod + 1);
dfs (2 * nod + 1 , conf + (1 << p2) , p2 + 1 , val , linit , dif);
}
else {
w[nod].push_back(2 * nod);
w[nod].push_back(2 * nod + 1);
dfs (2 * nod + 1 , conf + (1 << p2) , p2 + 1 , val , linit , dif);
dfs (2 * nod , conf , p2 + 1 , val , linit , dif);
}
}
}
void dfs_put (int nod){
int i , vecin;
f[nod] = 1;
v[++elem] = nod;
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin > 0 && !f[vecin])
dfs_put(vecin);
}
}
void dfs_solve (int nod){
int i , vecin , val;
f[nod] = 1;
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin > 0)
val = -newp[vecin];
else val = -vecin;
if (i == 0)
x[ newp[nod] - 1 ] = val;
else y[ newp[nod] - 1 ] = val;
if (vecin > 0 && !f[vecin])
dfs_solve(vecin);
}
}
void create_circuit(int m, vector<int> a) {
int n = a.size() , i , l , poz;
vector <int> c;
c.push_back(-1);
for (i = 1 ; i <= m ; i++)
c.push_back(-1);
/// trb sa vezi cate noduri nu iti sunt necesare
l = 0;
while ((1 << l) <= n){
l++;
}
dfs (1 , 0 , 0 , (1 << l) - 1 , l , (1 << l) - n - 1);
sort (order + 1 , order + leaf + 1);
a.push_back(0);
poz = 0;
for (i = 1 ; i <= leaf ; i++){
if (exists[ order[i].second ]){
w[ order[i].second ].push_back(-a[poz]);
poz++;
}
}
memset ( f , 0 , sizeof(f) );
dfs_put (1);
sort (v + 1 , v + elem + 1);
for (i = 1 ; i <= elem ; i++){
newp[v[i]] = i;
}
memset ( f , 0 , sizeof(f) );
x.resize(elem , 0);
y.resize(elem , 0);
dfs_solve(1);
answer (c , x , y);
}
