#include "doll.h"
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#define X first
#define Y second
#define PB push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...) printf("")
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, int*> pip;
const int N = 2e5 + 10;
int n, m;
int cnt = 0, cntl, rgt[2 * N], lft[2 * N];
vector<int> C, X, Y;
vector<pip> p;
int rec(int k, int l) {
int u = cnt++, siz = 1 << l;
if(siz == 2) {
if(k == 2) { p.PB({cntl++, &lft[u]}); }
p.PB({cntl++, &rgt[u]});
return u;
}
if(k <= siz / 2) {
lft[u] = -1;
} else {
lft[u] = -(rec(k - siz / 2, l - 1) + 1);
}
rgt[u] = -(rec(min(k, siz / 2), l - 1) + 1);
return u;
}
void create_circuit(int mm, vector<int> niz) {
niz.PB(0);
n = niz.size();
m = mm;
C.resize(m + 1, -1);
memset(rgt, -1, sizeof(rgt));
memset(lft, -1, sizeof(lft));
if(niz.size() & 1) {
C[0] = niz[0];
niz.erase(niz.begin());
--n;
}
int lg = 0;
for(; (1 << lg) < n; ++lg);
cntl = (1 << lg) - n;
rec(n, lg);
sort(p.begin(), p.end(), [&lg](pip a, pip b) {
for(int i = 0; i <= lg; ++i) {
if((a.X & (1 << i)) != (b.X & (1 << i))) {
return b.X & (1 << i);
}
}
return 0;
});
for(int i = 0; i < n; ++i) {
*p[i].Y = niz[i];
}
X.resize(cnt);
Y.resize(cnt);
for(int i = 0; i < cnt; ++i) {
X[i] = lft[i];
Y[i] = rgt[i];
}
// for(int i = 0; i < cnt; ++i) {
// debug("%d : %d %d\n", -(i + 1), X[i], Y[i]);
// }
// for(int i = 0; i < m + 1; ++i) {
// debug("%d %d\n", i, C[i]);
// }
//debug("bla\n");
answer(C, X, Y);
}
