#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> C, X, Y, Q[200200];
int l;
vector<int> nxt;
void build_tree(int i, int root, int H, int val, bool on){
if (on && (val&(1<<H))) X[i] = -root;
else if (H){
X.push_back(1e9);
Y.push_back(1e9);
X[i] = -(int)X.size();
build_tree((int)X.size()-1, root, H-1, val, 0);
}
if (H){
X.push_back(1e9);
Y.push_back(1e9);
Y[i] = -(int)X.size();
build_tree((int)X.size()-1, root, H-1, val, on&1);
}
}
bool ON[400400];
void getidx(int i){
ON[i] ^= 1;
if (ON[i]){
if (X[i]==1e9) X[i] = nxt[l++];
else getidx(-X[i]-1);
}
else{
if (Y[i]==1e9) Y[i] = nxt[l++];
else getidx(-Y[i]-1);
}
}
void create_circuit(int M, std::vector<int> A) {
int n = A.size();
C.resize(M+1);
A.push_back(0);
C[0] = A[0];
for (int i=0;i<n;i++) Q[A[i]].push_back(A[i+1]);
for (int i=1;i<=M;i++){
if (Q[i].empty()) continue;
if (Q[i].size()==1) {C[i] = Q[i][0]; continue;}
l = 0, nxt = Q[i];
X.push_back(1e9); Y.push_back(1e9);
C[i] = -(int)X.size();
int t = 1, h = 0, R = (int)X.size()-1;
for (;t<(int)Q[i].size();t<<=1, h++);
build_tree(R, R+1, h-1, t-(int)Q[i].size(), 1);
while(l<(int)nxt.size()) getidx(R);
}
answer(C, X, Y);
}
