// 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;
vector<int> ls[maxn];
vector<int> adj[maxn], Ax, A1, A2;
void solve(int v, vector<int> ls) {
if (len(ls) == 0) {
adj[v].pb(v);
return ;
}
else {
bool flag = 1; int val = ls[0];
for (int i = 0; i < len(ls); i++) {
if (ls[i] != val) {
flag = 0;
break;
}
}
if (flag) {
adj[v].pb(ls[0]);
return ;
}
}
int u = sz++; adj[v].pb(u);
int R = (1 << __lg(len(ls)));
if (R != len(ls)) {
R *= 2; int k = R - len(ls);
vector<int> lsx;
lsx.resize(R); fill(all(lsx), -1);
while (k > 0) {
int j = __builtin_ctz(k); k ^= (1 << j);
int w = (R / (1 << j));
for (int i = (w / 2); i < R; i += w) lsx[i] = u;
}
int j = 0;
for (int i = 0; i < len(lsx); i++) {
if (lsx[i] == -1) {
lsx[i] = ls[j]; j++;
}
}
ls = lsx;
}
vector<int> ls0, ls1;
for (int i = 0; i < len(ls); i++) {
if (i % 2 == 0) ls0.pb(ls[i]);
else ls1.pb(ls[i]);
}
solve(u, ls0); solve(u, ls1);
}
void create_circuit(int Mx, vector<int> A) {
m = Mx; n = len(A);
ls[0].pb(A[0]);
for (int i = 1; i < n; i++) {
ls[A[i - 1]].pb(A[i]);
}
ls[A.back()].pb(0);
sz = m + 1;
for (int i = 0; i <= m; i++) {
solve(i, ls[i]);
}
Ax.resize(m + 1); A1.resize(sz - m - 1); A2.resize(sz - m - 1);
for (int i = 0; i <= m; i++) {
int u = adj[i][0];
if (u <= m) Ax[i] = u;
else Ax[i] = -(u - m);
}
for (int i = m + 1; i < sz; i++) {
int j = i - m - 1;
int u1 = adj[i][0], u2 = adj[i][1];
if (u1 <= m) A1[j] = u1;
else A1[j] = -(u1 - m);
if (u2 <= m) A2[j] = u2;
else A2[j] = -(u2 - m);
}
answer(Ax, A1, A2);
}
