#include <bits/stdc++.h>
#include "doll.h"
#define fi first
#define se second
#define p_b push_back
#define m_p make_pair
#define sz(x) (int)x.size()
#define pii pair <int, int>
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const ll inf = 1e7;
ll stn = 0, id = -1, uk;
vector <int> x, y, st, l, r, idx, le, ri;
int build(int v, int tl, int tr){
le[v] = tl;
ri[v] = tr;
if(tl == tr)return 0;
else{
int tm = (tl + tr) >> 1;
int t = stn, d = id;
idx[v] = t;
stn++;
id--;
l[v] = sz(l);
l.p_b(0);
r.p_b(0);
le.p_b(0);
ri.p_b(0);
x.p_b(0);
y.p_b(0);
idx.p_b(0);
r[v] = sz(l);
l.p_b(0);
r.p_b(0);
le.p_b(0);
ri.p_b(0);
idx.p_b(0);
int vv = build(l[v], tl, tm);
x[t] = vv;
vv = build(r[v], tm + 1, tr);
y[t] = vv;
return d;
}
}
int dfs(int v){
if(le[v] == ri[v])return st[uk++];
else{
int t = idx[v];
int V = dfs(l[v]);
if(V != inf)x[t] = V;
swap(l[v], r[v]);
swap(x[t], y[t]);
return inf;
}
}
void create_circuit(int M, vector<int> A) {
int n = sz(A);
stn = 0;
id = -1;
std::vector<int> C(M + 1);
vector <vector <int>> v(M + 1);
A.p_b(0);
for(int i = 0; i < n; i++){
v[A[i]].p_b(A[i + 1]);
}
C[0] = A[0];
for(int i = 1; i <= M; i++){
st = v[i];
if(st.empty())C[i] = 0;
else if(sz(st) == 1)C[i] = st[0];
else{
l.clear();
le.clear();
r.clear();
ri.clear();
uk = 0;
l.p_b(0);
le.p_b(0);
r.p_b(0);
ri.p_b(0);
idx.p_b(0);
C[i] = build(0, 0, sz(st) - 1);
uk = 0;
for(int i = 0; i < sz(st); i++){
dfs(0);
}
}
}
answer(C, x, y);
}
