#include "doll.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll int
#define all(a) (a).begin(), (a).end()
void create_circuit(int M, vector<int> A) {
int N = A.size();
A.push_back(0);
vector<int> C(M + 1);
vector<vector<pair<int,int>>> con(M+1);
for(ll i = 0; i < N; i++)
{
con[A[i]].emplace_back(i, A[i+1]);
}
int nx = -1;
vector<int> X(N + 50), Y(N + 50);
C[0] = A[0];
vector<pair<int,int>> nc;
for(int i = 1; i <= M; i++)
{
if(con[i].size() == 0)
{
C[i] = 0;
}
else if(con[i].size() == 1)
{
C[i] = con[i][0].second;
}
else
{
C[i] = -1;
for(auto e : con[i]) nc.emplace_back(e);
}
con[i].clear();
}
sort(all(nc), greater<pair<int,int>>());
int len = nc.size();
int depth = (__builtin_popcount(len) == 1) ?
__bit_width((uint32_t)len)-1 :
__bit_width((uint32_t)len);
int first_node = -1;
vector<pair<ll,pair<ll, bool>>> tm;
function<int(int, int)> prop = [&](int val, int dep) -> int
{
int node = nx;
nx--;
if(dep == depth-1)
{
int val1 = val;
int val2 = val + (1<<dep);
if(tm.size() < len)
{
tm.push_back({val1, {node, 0}});
tm.push_back({val2, {node, 1}});
return node;
}
else
{
nx++;
return first_node;
}
}
else
{
int y = prop(val+(1<<dep), dep+1);
int x = prop(val, dep+1);
X[-(node+1)] = x;
Y[-(node+1)] = y;
return node;
}
};
prop(0, 0);
sort(all(tm), greater<pair<ll, pair<ll, bool>>>());
while(nc.size() != 1)
{
// cout << nc.back().first << " " << nc.back().second << " || " << tm.back().first << " " << tm.back().second.first << " " << tm.back().second.second<< "\n";
int to = nc.back().second;
nc.pop_back();
auto [node, r] = tm.back().second;
tm.pop_back();
if(r) Y[-(node+1)] = to;
else X[-(node+1)] = to;
}
while(tm.size() != 1)
{
// cout << "filling\n";
auto [node, r] = tm.back().second;
tm.pop_back();
if(r) Y[-(node+1)] = -1;
else X[-(node+1)] = -1;
}
// cout << "last:\n";
// cout << nc.back().first << " " << nc.back().second << " || " << tm.back().first << " " << tm.back().second.first << " " << tm.back().second.second<< "\n";
auto [node, r] = tm.back().second;
if(r) Y[-(node+1)] = nc.back().second;
else X[-(node+1)] = nc.back().second;
X.resize(-(nx+1));
Y.resize(-(nx+1));
answer(C, X, Y);
}
