// In the name of Allah
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 4;
int n, m, sz, szx; int A[maxn];
vector<int> Ax, ls;
vector<int> Rx, R1, R2;
void oprx(int l, int r) {
if (r - l <= 1) return ;
int mid = (l + r) / 2;
oprx(l, mid); oprx(mid, r);
vector<int> A1, A2;
for (int i = l; i < r; i++) {
if (i < mid) A1.pb(Ax[i]);
else A2.pb(Ax[i]);
}
for (int i = l; i < r; i++) {
if ((i - l) % 2 == 0) Ax[i] = A1[(i - l) / 2];
else Ax[i] = A2[(i - l) / 2];
}
}
int addx() {
szx++; R1.pb(-1); R2.pb(-1);
return -szx;
}
int solvex(vector<int> A) {
if (*max_element(all(A)) == *min_element(all(A))) {
return A[0];
}
int v = addx();
vector<int> A1, A2;
for (int i = 0; i < len(A); i++) {
if (i % 2 == 0) A1.pb(A[i]);
else A2.pb(A[i]);
}
int u1 = solvex(A1); int u2 = solvex(A2);
int j = (-v) - 1;
R1[j] = u1; R2[j] = u2;
return v;
}
void create_circuit(int M, vector<int> Fx) {
n = len(Fx); m = M;
for (int i = 0; i < n; i++) A[i] = Fx[i];
A[n] = 0; n++;
sz = (1 << __lg(n));
if (sz < n) sz *= 2;
for (int i = 0; i < sz; i++) {
if (i < sz - n) Ax.pb(0);
else Ax.pb(1);
}
oprx(0, sz);
int j = 0; ls.resize(sz);
for (int i = 0; i < sz; i++) {
if (Ax[i] == 0) ls[i] = -1;
else {
ls[i] = A[j]; j++;
}
}
int v = solvex(ls);
Rx.resize(m + 1); fill(all(Rx), -1);
answer(Rx, R1, R2);
}
