#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int gen(vector<int> &after, vector<int> &X, vector<int> &Y, int &S) {
int sz = after.size();
if (sz == 0) {
return 0;
}
if (sz == 1) {
return after[0];
}
else {
int b = 0;
while ((1<<b) < sz) {
b++;
}
int pw = (1<<b);
vector<int> bits(pw);
for (int i=0; i<pw; i++) {
bits[i] = (bits[i/2])/2 | ((i&1) << (b-1));
}
int id = --S;
for (int i=0; i<(pw-1)/2; i++) {
X.push_back(--S);
Y.push_back(--S);
}
for (int i=0; i<pw; i++) {
vector<int> &aux = (i%2 ? Y : X);
if (bits[i] < (pw-sz)) {
aux.push_back(id);
}
else {
aux.push_back(after[bits[i] - (pw-sz)]);
}
}
return id;
}
}
void create_circuit(int M, std::vector<int> A) {
A.push_back(0);
int N = A.size();
vector<int> C(M+1);
vector<int> X, Y;
vector<vector<int>> after(M+1);
for (int i=0; i<N; i++) {
after[A[i]].push_back(A[(i+1)%N]);
}
int S=0;
for (int i=0; i<M+1; i++) {
C[i] = gen(after[i], X, Y, S);
}
answer(C, X, Y);
}
