#include "doll.h"
#include "bits/stdc++.h"
using namespace std;
void create_circuit(int M, std::vector<int> A);
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int lg(int x) {
return 32 - __builtin_clz(x) - 1;
}
vector<int> X, Y;
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
int freq[M+1];
for(int i=1; i<=M; i++) freq[i] = 0;
for(int i=0; i<N; i++) freq[A[i]]++;
int ma = 0;
for(int i=1; i<=M; i++) ma = max(ma, freq[i]);
vector<int> C(M + 1);
for(int i=0; i<=M; i++) C[i] = 0;
C[0] = A[0];
vector<int> sequence;
vector<int> empty;
for(int i=0; i+1<N; i++) {
sequence.push_back(A[i+1]);
}
if(ma <= 1) {
for(int i=0; i<N; i++) C[A[i]] = (i+1 == N ? 0 : A[i+1]);
answer(C, empty, empty);
return;
}
for(int i=1; i<=M; i++) C[i] = -1;
if(N % 2 == 0) sequence.push_back(-1);
if(ma <= 4 || N == 16 || M == 1) {
X.resize(N + lg(N));
Y.resize(N + lg(N));
}
else {
if(N >= 200000) {
X.resize(N + lg(N) + 1);
Y.resize(N + lg(N) + 1);
}
}
int L = sequence.size();
int bitcount = 1 + lg(L);
int nxt = 0;
int uwu = bitcount;
for(int i=bitcount-1; i>=0; i--) {
int val = (1 << i);
Y[nxt] = (i == 0 ? 12073412 : nxt+1);
// tree of size val: val - 1 swithces
if(!(L & (1 << i))) X[nxt] = 0;
else X[nxt] = uwu;
nxt++;
if(!(L & (1 << i))) continue;
int seq = uwu + 1;
for(int j=uwu; j<uwu+val/2-1; j++) {
X[j] = seq;
seq++;
Y[j] = seq;
seq++;
}
for(int j=uwu+val/2-1; j<uwu+val-1; j++) {
X[j] = Y[j] = -1;
}
uwu += val - 1;
}
// Non-negative: switch
// -1: to-be trigger
// -2: origin
int id = 0;
int visits = 0;
int state[N + lg(N)];
for(int i=0; i<N+lg(N); i++) state[i] = 0;
while(1) {
int cur = 0;
int prv;
char u;
bool done = 0;
while(1) {
//if(cur == 12073412) cout << "end\n";
//else if(cur != -1) cout << -(cur + 1) << "\n";
if(cur == -1) {
if(u == 'X') X[prv] = -(sequence[id] + 1);
else Y[prv] = -(sequence[id] + 1);
// cout << sequence[id] << "\n";
id++;
break;
}
else if(cur == 12073412) {
done = 1;
break;
}
else if(state[cur] == 0) {
state[cur] ^= 1;
prv = cur;
u = 'X';
cur = X[cur];
}
else {
state[cur] ^= 1;
prv = cur;
u = 'Y';
cur = Y[cur];
}
}
visits++;
if(done) break;
}
for(int i=0; i<N+lg(N); i++) {
if(X[i] == 12073412) X[i] = 0;
else X[i] = -(X[i] + 1);
if(Y[i] == 12073412) Y[i] = 0;
else Y[i] = -(Y[i] + 1);
}
// for(int i=0; i<N+lg(N); i++) cout << state[i];
// cout << "\n";
answer(C, X, Y);
}
