#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define ALL(x) begin(x), end(x)
int rev_bin(int x, int bits) {
int r = 0;
for (int k = 0; k < bits; k++) {
if (x & (1<<k)) r += (1<<(bits-k-1));
}
return r;
}
void create_circuit(int M, std::vector<int> A)
{
int N = A.size();
A.push_back(0);
std::vector<int> C(M + 1);
std::vector<int> X, Y;
int idx = -1;
vvi out(M+1);
for (int i = 0; i < N; i++) out[A[i]].push_back(A[i+1]);
C[0] = A[0];
for (int i = 1; i <= M; i++) {
if (out[i].size() == 0) C[i] = i;
else if (out[i].size() == 1) C[i] = out[i][0];
else {
C[i] = idx;
int k = 0;
while ((1<<k) < out[i].size()) k++;
reverse(ALL(out[i]));
while (out[i].size() < (1<<k)) out[i].push_back(idx);
reverse(ALL(out[i]));
vi ass(2<<k);
for (int i = 1; i < (1<<k); i++) {
ass[i] = (idx--);
}
assert((1<<k) == out[i].size());
for (int j = 0; j < (1<<k); j++) ass[(1<<k) + rev_bin(j, k)] = out[i][j];
for (int i = 1; i < (1<<k); i++) {
X.push_back(ass[2*i]);
Y.push_back(ass[2*i+1]);
}
}
}
// cerr << "DEBUG INFO:\n";
// for (int x : C) cerr << x << ' '; cerr << '\n';
// for (int x : X) cerr << x << ' '; cerr << '\n';
// for (int x : Y) cerr << x << ' '; cerr << '\n';
answer(C, X, Y);
}
