#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair
#define eb emplace_back
using ii = pair<int, int>;
using iii = pair<ii, int>;
int swid = -1;
vector<int> sx, sy;
vector<iii> go(int h, int rem) {
vector<iii> ret;
int me = ++swid;
if (h == 1) {
ret.eb(mkp(me, 1), 2);
if (rem != 1) ret.eb(mkp(me, 0), 1);
return ret;
}
sy[me] = -swid - 2;
vector<iii> left, right = go(h - 1, rem);
if (rem > (1 << (h - 1))) {
sx[me] = -swid - 2;
left = go(h - 1, rem - (1 << (h - 1)));
}
for (auto &p : left) ret.eb(mkp(p.first.first, p.first.second), p.second * 2 - 1);
for (auto &p : right) ret.eb(mkp(p.first.first, p.first.second), p.second * 2);
return ret;
}
bool cmp(const iii &a, const iii &b) {
return a.second < b.second;
}
void create_circuit(int m, vector<int> seq) {
seq.eb(0);
int sz = seq.size();
vector<int> conn(m + 1, -1);
sx.assign(2 * sz, -1);
sy.assign(2 * sz, -1);
vector<iii> order = go(32 - __builtin_clz(sz), sz);
sort(order.begin(), order.end(), cmp);
for (int i = 0; i < sz; ++i) {
if (order[i].first.second) sy[order[i].first.first] = seq[i];
else sx[order[i].first.first] = seq[i];
}
while (!sx.empty() && sx.back() == -1 && sy.back() == -1) {
sx.pop_back(); sy.pop_back();
}
answer(conn, sx, sy);
}
