#include "doll.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
int sn = 0;
vector<int> C, X, Y;
const int PINF = numeric_limits<int>::max();
const int NINF = numeric_limits<int>::min();
const bool DEBUG = false;
void construct(int N, int d, int cd, int idx, int t) {
if (DEBUG) cout << N << " " << d << " " << cd << " " << idx << " " << t << endl;
if (t == 0) {
++sn;
C[idx] = -1;
X.emplace_back(PINF);
Y.emplace_back(PINF);
int K = 1;
while (K <= N) K <<= 1;
K >>= 1;
int psn = sn;
if (K == N) {
construct(N >> 1, d, cd + 1, psn - 1, 2);
construct(N >> 1, d, cd + 1, psn - 1, 4);
} else {
construct(K, d, cd + 1, psn - 1, 2);
construct(N - K, d, cd + 1, psn - 1, 1);
}
}
if (t == 2 || t == 4) {
if (N == 1) return;
++sn;
if (t == 2) X[idx] = -sn;
if (t == 4) Y[idx] = -sn;
X.emplace_back(PINF);
Y.emplace_back(PINF);
int psn = sn;
construct(N >> 1, d, cd + 1, psn - 1, 2);
construct(N >> 1, d, cd + 1, psn - 1, 4);
}
if (t == 1) {
int K = 1, c = 0;
while (K <= N) K <<= 1, ++c;
K >>= 1, --c;
++sn;
Y[idx] = -sn;
int psn = sn;
if (c + cd == d) {
if(N != K) {
X.emplace_back(PINF);
Y.emplace_back(PINF);
construct(K, d, cd + 1, psn - 1, 2);
construct(N - K, d, cd + 1, psn - 1, 1);
} else {
X.emplace_back(-1);
Y.emplace_back(PINF);
construct(N, d, cd + 1, psn - 1, 4);
}
} else {
X.emplace_back(-1);
Y.emplace_back(PINF);
construct(N, d, cd + 1, psn - 1, 1);
}
}
}
void fillc(int v, const vector<int>& nxt) {
int N = nxt.size();
vector<bool> swState(sn);
int ptr = 0;
for (int i = 0; i < N; i++) {
int x = C[v];
if (DEBUG) {
cout << endl;
cout << "ptr: " << ptr << endl;
}
while (true) {
x = -1 - x;
if (DEBUG) cout << x << " " << flush;
if (!swState[x]) {
if (DEBUG) cout << "X " << flush;
swState[x] = !swState[x];
if (X[x] != PINF)
x = X[x];
else {
X[x] = nxt[ptr];
++ptr;
break;
}
} else {
if (DEBUG) cout << "Y " << flush;
swState[x] = !swState[x];
if (Y[x] != PINF)
x = Y[x];
else {
Y[x] = nxt[ptr];
++ptr;
break;
}
}
}
}
if (DEBUG) cout << endl
<< endl;
}
bool destruct(int h) {
if (h >= -1) return false;
if (h == NINF) h = -1;
h = -1 - h;
if (X[h] == -1 && Y[h] == -1) return true;
if (destruct(X[h])) X[h] = -1;
if (destruct(Y[h])) Y[h] = -1;
if (X[h] == -1 && Y[h] == -1)
return true;
else
return false;
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
if (N == 1) {
C.resize(M + 1);
C[0] = A[0];
C[A[0]] = 0;
answer(C, X, Y);
return;
}
C.resize(M + 1);
C[0] = A[0];
A.emplace_back(0);
A.erase(A.begin(), A.begin() + 1);
int K = 1, d = 0;
while (K <= N) K <<= 1, ++d;
construct(N, d, 1, C[0], 0);
fillc(C[0], A);
for (int i = 1; i <= M; i++) C[i] = -1;
destruct(NINF);
K = X.size();
vector<int> Xret, Yret;
vector<int> alive;
for (int i = 0; i < K; i++) {
if (X[i] == -1 && Y[i] == -1) continue;
alive.emplace_back(i);
}
for (int i = 0; i < K; i++) {
if (X[i] == -1 && Y[i] == -1) continue;
if (X[i] < 0) {
Xret.emplace_back(-1 - (lower_bound(iterall(alive), -1 - X[i]) - alive.begin()));
} else {
Xret.emplace_back(X[i]);
}
if (Y[i] < 0) {
Yret.emplace_back(-1 - (lower_bound(iterall(alive), -1 - Y[i]) - alive.begin()));
} else {
Yret.emplace_back(Y[i]);
}
}
answer(C, Xret, Yret);
}
