#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
const int N = 2e5 + 10;
vi C , X ,Y, nx[N];
int n, cnt = 1;
inline int inve(int sz , int l) {
int res = 0;
rep(i , 0 , sz)
if (l & (1 << i))
res ^= (1 << (sz - 1 - i));
return res;
}
int build(int root, int lvl , int &g, int st = 0) {
if ((g >> lvl) & 1) {
g -= (1 << lvl);
return root;
}
if (lvl == 0) return -(N + st);
int me = cnt++;
X.pb(0);
Y.pb(0);
X[me - 1] = -build(root , lvl - 1, g , st);
Y[me - 1] = -build(root , lvl - 1, g , st + (1 << (lvl - 1)));
return me;
}
void build(vi vec) {
int z = 0;
while ((1 << z) < (int)vec.size()) z++;
int st = cnt;
int g = (1 << z) - vec.size();
build(cnt , z , g);
vi k;
rep(i , st - 1 , cnt - 1) {
if (X[i] >= N) k.pb(X[i] - N);
if (Y[i] >= N) k.pb(Y[i] - N);
}
auto cmp = [&](int a, int b) {
return inve(z , a) < inve(z , b);
};
sort(all(k) , cmp);
map<int , int> mp;
rep(i , 0 , k.size())
mp[k[i]] = i;
rep(i , st - 1, cnt - 1) {
if (X[i] >= N) X[i] = vec[mp[X[i] - N]];
if (Y[i] >= N) Y[i] = vec[mp[Y[i] - N]];
}
}
void create_circuit(int M, vi A) {
n = A.size();
A.pb(0);
rep(i , 0 , n)
nx[A[i]].pb(A[i + 1]);
C.resize(M + 1);
C[0] = A[0];
rep(i , 1 , M + 1) {
if (nx[i].empty())
C[i] = 0;
else if (nx[i].size() == 1) {
C[i] = nx[i][0];
}
else {
C[i] = -cnt;
build(nx[i]);
}
}
answer(C , X , Y);
return;
}
