#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 3e5 + 10;
int cnt[MX];
map<int, int> lf, rg;
vector<int> nx;
int _M, huge_mask = 0, tim = 0, mx_idx = 0;
vector<int> pos_starts;
int solve(int idx, int mask){
if(idx > 0 && !(huge_mask >> (mx_idx - idx) & 1)){
huge_mask ^= 1 << (mx_idx - idx);
return -1;
}else if(idx == mx_idx){
pos_starts.push_back(mask);
return 2 * _M + mask + 10;
}else{
++tim; int curr = -tim;
lf[curr] = solve(idx + 1, mask);
rg[curr] = solve(idx + 1, mask + (1 << idx));
return curr;
}
}
void create_circuit(int M, vector<int> A) {
_M = M;
int N = A.size();
vector<int> C(M + 1), X, Y;
if(N == 1){
C[0] = A[0];
for(int i = 1; i <= M; i++) C[i] = 0;
answer(C, X, Y);
return;
}
C[0] = A[0]; cnt[A[0]]++;
for(int i = 1; i < N; i++) cnt[A[i]]++, nx.push_back(A[i]);
nx.push_back(0);
huge_mask = N - 1;
for(int j = 0; j < 20; j++){
if((1 << j) > huge_mask){
mx_idx = j;
break;
}
}
for(int i = 1; i <= M; i++){
if(cnt[i] == 0) C[i] = 0;
else C[i] = -1;
}
solve(0, 0);
sort(pos_starts.begin(), pos_starts.end());
for(int i = -1; i >= -tim; i--){
if(lf[i] > M){
int curr_mask = lf[i] - 2 * M - 10;
int idx = lower_bound(pos_starts.begin(), pos_starts.end(), curr_mask) - pos_starts.begin();
X.push_back(nx[idx]);
}else{
X.push_back(lf[i]);
}
if(rg[i] > M){
int curr_mask = rg[i] - 2 * M - 10;
int idx = lower_bound(pos_starts.begin(), pos_starts.end(), curr_mask) - pos_starts.begin();
Y.push_back(nx[idx]);
}else{
Y.push_back(rg[i]);
}
}
answer(C, X, Y);
}
