#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int t = 0;
vector<int> X, Y, C;
int create_2pow(int c, int i, int tl, int tr, int &diff, vector<pair<int, int>> &vec, int self = INT_MIN) {
if (tr - tl <= diff) {
diff -= tr - tl;
return self;
}
if (tr - tl == 2) {
int ret = ++t;
vec.push_back({c, ret});
vec.push_back({c + (1 << i), -ret});
return -ret;
}
int ret = ++t;
if (self == INT_MIN)
self = -ret;
int tm = (tl + tr) / 2;
X[ret - 1] = create_2pow(c, i + 1, tl, tm, diff, vec, self), Y[ret - 1] = create_2pow(c + (1 << i), i + 1,tm, tr, diff, vec, self);
return -ret;
}
int create(vector<int> &leaf) {
if (leaf.size() == 1)
return leaf[0];
int n = 1 << 32 - __builtin_clz(leaf.size() - 1);
int diff = n - leaf.size();
vector<pair<int, int>> vec;
int ret = create_2pow(0, 0, 0, n, diff, vec);
sort(vec.begin(), vec.end());
if (diff) {
leaf.push_back(ret);
swap(leaf[leaf.size() - 1], leaf[leaf.size() - 2]);
}
for (int i = 0; i < vec.size(); i++) {
int ret = vec[i].second;
if (ret > 0)
X[ret - 1] = leaf[i];
else
Y[-ret - 1] = leaf[i];
}
return ret;
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
A.push_back(0);
X.resize(2 * N), Y.resize(2 * N);
int x = create(A);
C.resize(M + 1, x);
// map<int, vector<int>> mp;
// for (int i = 1; i <= N; i++)
// mp[A[i - 1]].push_back(A[i]);
// for (auto [v, leaf] : mp)
// C[v] = create(leaf);
X.resize(t), Y.resize(t);
answer(C, X, Y);
}
