#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;
int cnt, m;
void add(int ver, int root, int depth, int& tot, vector<int>& X, vector<int>& Y, vector<int>& state){
if(!tot){
if(Y[ver-m-1]==-1) Y[ver-m-1]=root;
if(X[ver-m-1]==-1) X[ver-m-1]=root;
return;
}
if(!depth){
tot--;
if(!tot) X[ver-m-1]=root;
else tot--;
return;
}
Y[ver-m-1]=++cnt;
X.pb(-1); Y.pb(-1);
state.pb(0);
add(cnt, root, depth-1, tot, X, Y, state);
if(!tot) X[ver-m-1]=root;
else{
X[ver-m-1]=++cnt;
X.pb(-1); Y.pb(-1);
state.pb(0);
add(cnt, root, depth-1, tot, X, Y, state);
}
}
void calc(int p, int qnt, vector<int>& C, vector<int>& X, vector<int>& Y, vector<int>& state){
if(qnt==1) return;
int cam=0;
while((1<<cam)<qnt) cam++;
C[p]=++cnt;
X.pb(-1); Y.pb(-1);
state.pb(0);
add(cnt, cnt, cam-1, qnt, X, Y, state);
}
void create_circuit(int M, vector<int> A) {
cnt=M;
m=M;
A.pb(0);
vector<int> C(M+1, -1), X, Y, freq(M+1, 0), state;
for(auto u : A) freq[u]++;
int curr=0;
for(auto u : A){
if(C[curr]==-1) calc(curr, freq[curr], C, X, Y, state);
if(C[curr]==-1){
C[curr]=u;
curr=u;
continue;
}
curr=C[curr];
while(1){
if(!state[curr-m-1]){
state[curr-m-1]=1-state[curr-m-1];
if(X[curr-m-1]==-1){
X[curr-m-1]=u;
break;
}
else curr=X[curr-m-1];
}
else{
state[curr-m-1]=1-state[curr-m-1];
if(Y[curr-m-1]==-1){
Y[curr-m-1]=u;
break;
}
else curr=Y[curr-m-1];
}
}
curr=u;
}
for(auto& u : C){
if(u>m) u=m-u;
else if(u==-1) u=0;
}
for(auto& u : X)
if(u>m) u=m-u;
for(auto& u : Y)
if(u>m) u=m-u;
answer(C, X, Y);
}
