#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 12;
vector<int> g[maxn];
int n, m;
vector<int> find(vector<int> v) {
if((int)v.size() <= 1) return v;
vector<int> res, a, b;
for(int i = 0; i < v.size(); i += 2) {
a.push_back(v[i]);
}
for(int i = 1; i < v.size(); i += 2) {
b.push_back(v[i]);
}
a = find(a), b = find(b);
for(int x : a) {
res.push_back(x);
}
for(int x : b) {
res.push_back(x);
}
return res;
}
void create_circuit(int M, std::vector<int> a) {
n = (int)a.size();
m = M;
vector<int> c(m + 1), x, y;
c[0] = a[0];
for(int i = 0; i < n - 1; i++) {
g[a[i]].push_back(a[i + 1]);
}
g[a[n - 1]].push_back(0);
for(int i = 1; i <= m; i++) {
if((int)g[i].size() == 0) {
continue;
}
if((int)g[i].size() == 1) {
c[i] = g[i][0];
continue;
}
int t = 1, init = (int)x.size();
while(t < (int)g[i].size()) {
t <<= 1;
}
c[i] = -(init + 1);
int sz = t - (int)g[i].size();
for(int j = 1; j < t; j++) {
x.push_back(0);
y.push_back(0);
}
reverse(g[i].begin(), g[i].end());
for(int j = 0; j < sz; j++) {
g[i].push_back(-(init + t + j));
}
reverse(g[i].begin(), g[i].end());
g[i] = find(g[i]);
for(int j = 1; j < t; j++) {
x[init + j - 1] = -(2 * j + init);
y[init + j - 1] = -(2 * j + 1 + init);
if(2 * j >= t) {
x[init + j - 1] = g[i][2 * j - t];
y[init + j - 1] = g[i][2 * j + 1 - t];
if(x[init + j - 1] < 0) x[init + j - 1] = -(init + 1);
if(y[init + j - 1] < 0) y[init + j - 1] = -(init + 1);
}
}
}
answer(c, x, y);
}
