#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxvr = 2e5 + 100;
vector<int> num(maxvr); // naozajstne cisla vrcholov v strome. Teda switche budu zaporne a prvych m cisel budu v skutocnosti nieco ine
vector<vector<int> > g(maxvr);
int n, m, s, lf, root, first; // mame fiktivny n+1-vy trigger na to aby sme sa vratili do 0
int dfs(int l, int r)
{
if (r < first) return root;
if (l == r) return lf++;
int now = s;
s++;
g[now].push_back(dfs(l, (l+r)/2));
g[now].push_back(dfs((l+r)/2+1, r));
return now;
}
vector<int> stav(maxvr, 0);
int get_next() // ideme na nasledujuci vrchol ktory ma cislo mensie ako n
{
int vr = root;
while (vr >= n)
{
int nw = g[vr][stav[vr]];
stav[vr] ^= 1;
vr = nw;
}
return vr;
}
void create_circuit(int M, vector<int> a) {
m = M;
a.push_back(0), n = a.size();
lf = 0, s = n;
int n2 = 1;
while (n2 < n) n2 <<= 1;
root = n, first = n2 - n; dfs(0, n2 - 1);
for (int i = 0; i < n; i++)
{
int vr = get_next();
num[vr] = a[i];
}
for (int i = n; i < s; i++)
{
num[i] = -(i - (n-1));
}
vector<int> c(m+1, num[root]), x(s-n), y(s-n);
for (int i = n; i < s; i++)
{
x[i-n] = num[g[i][0]];
y[i-n] = num[g[i][1]];
}
/*for (int i = 0; i <= m; i++) cout << i << " " << c[i] << endl;
for (int i = 0; i < x.size(); i++)
{
cout << -(i+1) << " " << x[i] << endl;
cout << -(i+1) << " " << y[i] << endl;
}*/
answer(c, x, y);
}
