#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();
int reidx[m + 1];
for (int i = 1; i <= m; i++) reidx[i] = 0;
for (int x : a) reidx[x]++;
int bruh[m + 1];
for (int i = 1; i < n; i++) bruh[a[i - 1]] = a[i];
bruh[a[n - 1]] = 0;
int base = 0;
vector<int> C(m + 1);
C[0] = a[0];
for (int i = 1; i <= m; i++) {
if (reidx[i] == 0) {
C[i] = 0;
} else if (reidx[i] == 1) {
C[i] = bruh[i];
reidx[i] = 0;
} else if (reidx[i] >= 2) {
reidx[i] = ++base;
C[i] = -reidx[i];
}
}
vector<int> sto[base + 1];
for (int i = 1; i < n; i++) {
sto[reidx[a[i - 1]]].pb(a[i]);
}
sto[reidx[a[n - 1]]].pb(0);
// for (int i = 1; i <= m; i++) cerr << reidx[i] << ' ';
// cerr << endl;
// for (int i = 1; i <= base; i++) {
// for (int x : sto[i]) cerr << x << ' ';
// cerr << endl;
// }
vector<pii> nxt[2];
bool flag = false;
vector<int> access;
vector<bool> state;
auto gentree = [&](auto&& self, int sz) {
if (sz == 2) {
nxt[flag] = {{-2, -2}};
return;
}
self(self, (sz + 1) / 2);
flag ^= 1;
nxt[flag] = {{-1, -1}};
for (int i = 0; i < 2; i++) {
int buff = nxt[flag].size();
if (i == 0) nxt[flag][0].ff = buff;
else nxt[flag][0].ss = buff;
for (pii cur : nxt[flag ^ 1]) {
if (cur.ff != -2) cur.ff += buff;
if (cur.ss != -2) cur.ss += buff;
nxt[flag].pb(cur);
}
}
if (sz % 2 == 1) {
access.resize(nxt[flag].size(), 0);
int st = 0;
while (true) {
if (!access[st]) {
access[st] = !access[st];
if (nxt[flag][st].ff == -2) {
nxt[flag][st].ff = 0; break;
}
st = nxt[flag][st].ff;
} else {
access[st] = !access[st];
if (nxt[flag][st].ss == -2) {
nxt[flag][st].ss = 0; break;
}
st = nxt[flag][st].ss;
}
}
}
};
auto gen = [&](auto&& self, int sz) -> int {
nxt[0].clear(); nxt[1].clear();
flag = false;
gentree(gentree, sz);
int used = nxt[flag].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" << endl;
do {
int st = 0;
while (true) {
if (!state[st]) {
state[st] = !state[st]; cnt++;
if (nxt[flag][st].ff == -2) {
nxt[flag][st].ff = dirs++;
break;
} else {
st = nxt[flag][st].ff;
}
} else {
state[st] = !state[st]; cnt--;
if (nxt[flag][st].ss == -2) {
nxt[flag][st].ss = dirs++;
break;
} else {
st = nxt[flag][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(base), Y(base);
int cnt = base;
for (int i = 1; i <= base; i++) {
if (sto[i].size() == 1) {
X[i - 1] = -i;
Y[i - 1] = sto[i].front();
continue;
}
int assign = gen(gen, sto[i].size());
auto decrypt = [&](int x) -> int {
if (x == 0) return -i;
else if (x < assign) return -(x + cnt);
else return sto[i][x - assign];
};
// cerr << "Gen " << i << ": \n";
// cerr << assign << endl;
// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
// cerr << "End of gen " << i << endl;
X[i - 1] = decrypt(nxt[flag][0].ff); Y[i - 1] = decrypt(nxt[flag][0].ss);
for (int j = 1; j < (int)(nxt[flag].size()); j++) {
// cerr << "decrypt " << nxt[j].ff << ' ' << decrypt(nxt[j].ff) << endl;
X.pb(decrypt(nxt[flag][j].ff));
Y.pb(decrypt(nxt[flag][j].ss));
}
cnt = (int)(X.size());
}
answer(C, X, Y);
}
