#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
void create_circuit(int m, vector<int> a) {
int n = a.size();
vector<int> c(m + 1);
a.push_back(0);
c[0] = a[0];
vector<vector<int>> pos(m + 1);
for(int i = 0; i < n; i ++){
pos[a[i]].push_back(i);
}
vector<int> x, y;
auto addx = [&](int from, int to)->void{
while(len(x) < -from) x.push_back(0);
x[-from - 1] = to;
};
auto addy = [&](int from, int to)->void{
while(len(y) < -from) y.push_back(0);
y[-from - 1] = to;
};
for(int i = 1; i <= m; i ++){
if(len(pos[i]) == 0) continue;
if(len(pos[i]) == 1){
c[i] = a[pos[i][0] + 1];
continue;
}else{
int b = 32 - __builtin_clz(len(pos[i]) - 1);
int cur = -len(x);
c[i] = cur - 1;
for(int j = 0; j < len(pos[i]) - 1; j ++){
int x = 1;
for(int bit = 0; bit < b; bit ++){
if(j >> bit & 1){
if(bit < b - 1){
addy(cur - x, cur - (x * 2 + 1));
}else{
addy(cur - x, a[pos[i][j] + 1]);
}
x = x * 2 + 1;
}else{
if(bit < b - 1)
addx(cur - x, cur - x * 2);
else
addx(cur - x, a[pos[i][j] + 1]);
x *= 2;
}
}
}
for(int j = len(pos[i]) - 1; j < (1 << b) - 1; j ++){
int x = 1;
for(int bit = 0; bit < b; bit ++){
if(j >> bit & 1){
if(bit < b - 1){
addy(cur - x, cur - (x * 2 + 1));
}else{
addy(cur - x, cur - 1);
}
x = x * 2 + 1;
}else{
if(bit < b - 1){
addx(cur - x, cur - x * 2);
}else
addx(cur - x, cur - 1);
x = x * 2;
}
}
}
int x = 1;
for(int bit = 0; bit < b; bit ++){
if(bit < b - 1){
addy(cur - x, cur - (x * 2 + 1));
}else addy(cur - x, a[pos[i].back() + 1]);
x = x * 2 + 1;
}
}
}
assert(len(x) <= 2 * n);
answer(c, x, y);
}
