#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define sz(x) (int)x.size()
// void answer(vector<int> &C, vector<int> tmp1, vector<int> tmp2)
// {
// for (auto &x : C)
// cout << x << " ";
// cout << '\n';
// for (auto x : tmp1)
// cout << x << " ";
// cout << '\n';
// for (auto x : tmp2)
// cout << x << " ";
// cout << '\n';
// }
int S;
vector<int> X, Y;
void build(int node, int mx_node)
{
if (node == 1)
X.resize(sz(X) + mx_node - 1, -S - node), Y.resize(sz(Y) + mx_node - 1, -S - node);
if (node * 2 >= mx_node)
return;
X[S + node - 1] = -S - node * 2;
Y[S + node - 1] = -S - node * 2 - 1;
build(2 * node, mx_node), build(2 * node + 1, mx_node);
}
void create_circuit(int M, vector<int> A)
{
int N = A.size();
vector<int> C(M + 1);
C[0] = A[0];
vector<int> make_switches;
set<int> seen;
vector<int> adj[M + 1];
adj[0].push_back(A[0]);
for (int i = 0; i < N; i++)
{
if (i < N - 1)
adj[A[i]].push_back(A[i + 1]);
else
adj[A[i]].push_back(0);
if (adj[A[i]].size() == 1)
C[A[i]] = adj[A[i]][0];
else if (seen.find(A[i]) == seen.end())
{
make_switches.push_back(A[i]);
seen.insert(A[i]);
}
}
int sz_switches = make_switches.size();
// for (auto x : make_switches)
// cout << x << " ";
// cout << '\n';
X.reserve(200005), Y.reserve(200005);
S = 0;
for (int i = 0; i < sz_switches; i++)
{
int root_trigger = make_switches[i];
int root_switch = -S - 1;
C[root_trigger] = root_switch;
int K = sz(adj[root_trigger]);
int log2;
for (int i = 0; i < 32; i++)
if ((1 << i) >= K)
{
log2 = i;
break;
}
build(1, 1 << log2);
auto leaves = adj[root_trigger];
reverse(leaves.begin(), leaves.end());
leaves.resize(1 << log2, root_switch);
reverse(leaves.begin(), leaves.end());
for (int i = 0; i < sz(leaves); i++)
{
// int mask = sz(leaves) - i - 1;
int mask = i;
int dest_node = 0;
for (int j = 0; j < log2; j++)
if ((mask >> j) & 1)
dest_node += 1 << (log2 - j - 1);
dest_node += (1 << log2);
int parent = (dest_node) / 2;
if (2 * parent == dest_node)
X[S + parent - 1] = leaves[i];
else
Y[S + parent - 1] = leaves[i];
// cout << "dest_node = " << dest_node << ", parent = " << parent << '\n';
// cout << "S = " << S << ", S + parent + 1 = " << S + parent + 1 << '\n';
}
S += (1 << log2) - 1;
}
answer(C, X, Y);
}
// int main()
// {
// vector<int> A = {1, 2, 1, 2, 1, 2, 1};
// int M = 2;
// create_circuit(M, A);
// return 0;
// }
