#include "doll.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 200000, M = 100000, L = 17, N_ = 1 << L; /* L = floor(log2(N))) */
int tmp[N_];
void split(int *aa, int n) {
int i, j, k;
for (i = 0, j = n / 2, k = 0; k < n; k++)
tmp[k % 2 == 0 ? i++ : j++] = aa[k];
memcpy(aa, tmp, n * sizeof *tmp);
}
vi xx(N * 2), yy(N * 2); int k;
int build(int *aa, int n) {
if (n == 1)
return aa[0];
else {
int u = k++;
split(aa, n);
xx[u] = build(aa, n / 2), yy[u] = build(aa + n / 2, n / 2);
return -(u + 1);
}
}
char used[L + 1]; int aaa[L + 1][N + 1], nn[L + 1];
void create_circuit(int m, vi aa) {
vi cc(m + 1, -1);
int n = aa.size(), l_, l, i, i_;
l_ = 1;
while (1 << l_ + 1 <= n + 1)
l_++;
if (1 << l_ == n + 1) {
for (i = 0; i <= n; i++)
aaa[0][i] = i == n ? 0 : aa[i];
build(aaa[0], n + 1);
} else {
for (l = 0; l <= l_; l++)
used[l] = (n + 1 & 1 << l_ - l) != 0;
for (l = 0; l <= l_; l++)
yy[l] = l == l_ ? 0 : -(l + 1 + 1);
for (i_ = 0, i = 0; i_ + 1 < 1 << l_ + 1; i_++) {
l = 0;
while (((i_ + 1) & 1 << l) == 0)
l++;
if (used[l])
aaa[l][nn[l]++] = i == n ? -1 : aa[i++];
}
k = l_ + 1;
for (l = 0; l <= l_; l++)
xx[l] = used[l] ? build(aaa[l], nn[l]) : -1;
}
xx.resize(k), yy.resize(k);
answer(cc, xx, yy);
}
