#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int M, vector<int> A) {
int N = A.size();
A.push_back(0);
vector<int> C(M + 1);
vector<int> X, Y;
vector<vector<int>> edge(M + 1);
for (int i = 0; i < N; i++) {
edge[A[i]].push_back(A[i + 1]);
}
C[0] = A[0];
for (int m = 1; m <= M; m++) {
if (edge[m].empty()) {}
else if (edge[m].size() == 1) {
C[m] = edge[m][0];
}
else {
int L = edge[m].size();
int b = 32 - __builtin_clz(L - 1);
int K = (1 << b);
C[m] = -X.size() - 1;
int xsz = X.size();
vector<bool> rem(K + 1);
vector<pair<int, int>> swt(K + 1);
for (int i = 1, l = b - 1; l >= 0; l--, i = i + i + 1) {
if ((K - L) & (1 << l)) {
swt[i].first = -1;
int ll = i + i, rr = ll + 1;
for (int c = 0; c < l; c++, ll += ll, rr += rr) {
for (int j = ll; j < rr; j++) {
rem[j] = true;
swt[j].first = swt[j].second = -1;
}
}
}
}
int idx = xsz + 1;
vector<int> nid(K + 1);
for (int i = 1; i <= K; i++) {
if (!rem[i]) {
nid[i] = idx++;
}
}
vector<int> v;
for (int i = 0; i < K; i++) {
bitset<32> bs(i);
for (int j = 0; j < b / 2; j++) {
bool t = bs[j];
bs[j] = bs[b - j - 1];
bs[b - j - 1] = t;
}
v.push_back(bs.to_ulong());
}
for (int i = 0, k = K / 2; i < K; i += 2, k++) {
if (swt[k].first == -1) {
v[i] = 1e9;
}
if (swt[k].second == -1) {
v[i + 1] = 1e9;
}
}
vector<int> stv = v;
sort(stv.begin(), stv.end());
for (int i = 0; i < K; i++) {
if (v[i] != 1e9) {
v[i] = lower_bound(stv.begin(), stv.end(), v[i]) - stv.begin();
}
}
vector<int> xid, yid;
for (int i = 0, k = K / 2; k < K; i += 2, k++) {
if (swt[k].first != -1) {
xid.push_back(v[i]);
}
if (swt[k].second != -1) {
yid.push_back(v[i + 1]);
}
}
reverse(xid.begin(), xid.end());
reverse(yid.begin(), yid.end());
for (int i = 1; i < K / 2; i++) {
if (!rem[i]) {
if (swt[i].first != -1) {
X.push_back(-nid[i + i]);
} else {
X.push_back(-xsz - 1);
}
if (swt[i].second != -1) {
Y.push_back(-nid[i + i + 1]);
} else {
Y.push_back(-xsz - 1);
}
}
}
for (int i = K / 2; i < K; i++) {
if (!rem[i]) {
if (swt[i].first != -1) {
X.push_back(edge[m][xid.back()]);
xid.pop_back();
} else {
X.push_back(-xsz - 1);
}
if (swt[i].second != -1) {
Y.push_back(edge[m][yid.back()]);
yid.pop_back();
} else {
Y.push_back(-xsz - 1);
}
}
}
Y.back() = edge[m][L - 1];
}
}
map<int, int> mp;
for (int i = 0; i < X.size(); i++) {
if (X[i] == Y[i]) {
mp[-i - 1] = X[i];
}
}
for (int &x : C) {
if (mp.count(x)) {
x = mp[x];
}
}
for (int &x : X) {
if (mp.count(x)) {
x = mp[x];
}
}
for (int &x : Y) {
if (mp.count(x)) {
x = mp[x];
}
}
vector<int> nX, nY;
map<int, int> nid;
for (int i = 0; i < X.size(); i++) {
if (!mp.count(-i - 1)) {
nid[-i - 1] = -nX.size() - 1;
nX.push_back(X[i]);
nY.push_back(Y[i]);
}
}
for (int &x : C) {
if (nid.count(x)) {
x = nid[x];
}
}
for (int &x : nX) {
if (nid.count(x)) {
x = nid[x];
}
}
for (int &x : nY) {
if (nid.count(x)) {
x = nid[x];
}
}
X = nX, Y = nY;
answer(C, X, Y);
}
