#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
void create_circuit(int m, vector<int> a) {
int n = a.size(); a.pb(0);
vector<int> C(m + 1, -1);
C[0] = a[0];
vector<pii> nxt;
vector<int> access;
vector<bool> state;
auto recur = [&](auto&& self, int ptr, int dep, int rem) -> int {
if (rem <= 0) {
nxt[ptr] = {ptr, 0};
return 0;
}
// assign right
if (dep == 1) {
nxt[ptr].ss = -2;
rem--;
} else {
int nptr = nxt.size();
nxt[ptr].ss = nptr;
nxt.pb({-1, -1});
rem = self(self, nptr, dep - 1, rem);
}
// assign left
if (rem == 0) {
nxt[ptr].ff = 0;
} else if (dep == 1) {
nxt[ptr].ff = -2;
rem--;
} else {
int nptr = nxt.size();
nxt[ptr].ff = nptr;
nxt.pb({-1, -1});
rem = self(self, nptr, dep - 1, rem);
}
return rem;
};
auto gen = [&](auto&& self, int sz) -> int {
int logsz = 1;
while ((1 << logsz) < sz) logsz++;
nxt = {{-1, -1}};
recur(recur, 0, logsz, sz);
int used = nxt.size();
int dirs = used;
state.resize(used, 0);
access.clear();
int cnt = 0;
// cerr << "Gen size " << sz << ":\n";
// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
// cerr << "End, nxt size = " << nxt.size() << endl;
do {
int st = 0;
while (true) {
if (!state[st]) {
state[st] = !state[st]; cnt++;
if (nxt[st].ff == -2) {
nxt[st].ff = dirs++;
break;
} else {
st = nxt[st].ff;
}
} else {
state[st] = !state[st]; cnt--;
if (nxt[st].ss == -2) {
nxt[st].ss = dirs++;
break;
} else {
st = nxt[st].ss;
}
}
}
} while (cnt > 0);
// cerr << "Gen size " << sz << ":\n";
// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
// cerr << "End" << endl;
return used;
};
vector<int> X, Y;
int assign = gen(gen, n);
auto decrypt = [&](int x) -> int {
if (x < assign) return -(x + 1);
else return a[x - assign + 1];
};
for (pii cur : nxt) {
X.pb(decrypt(cur.ff));
Y.pb(decrypt(cur.ss));
}
answer(C, X, Y);
}
