#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> A, C, X, Y, all_cnt, cur_cnt;
int N, M, K;
void build(int id, int depth, int cur) {
if (depth == K - 1) {
X[id - 1] = (cur < N - 1 ? A[cur + 1] : (cur == ((1 << K) - 1) ? 0 : -1));
cur += 1 << depth;
Y[id - 1] = (cur < N - 1 ? A[cur + 1] : (cur == ((1 << K) - 1) ? 0 : -1));
return;
}
X[id - 1] = -(id * 2);
Y[id - 1] = -(id * 2 + 1);
build(id * 2, depth + 1, cur);
build(id * 2 + 1, depth + 1, cur + (1 << depth));
}
void create_circuit(int _M, vector<int> _A) {
A = _A;
N = A.size();
M = _M;
all_cnt.resize(M + 1);
cur_cnt.resize(M + 1);
for (int i = 0; i < N; i++) {
all_cnt[A[i]]++;
}
bool sub3 = true;
for (int i = 1; i <= M; i++) {
if (all_cnt[i] > 3) {
sub3 = false;
break;
}
}
if (sub3) {
C.resize(M + 1);
C[0] = A[0];
int K = 0;
for (int i = 1; i <= M; i++) {
if (all_cnt[i] == 2) {
K++;
C[i] = -K;
X.push_back(0);
Y.push_back(0);
}
if (all_cnt[i] == 3) {
K++;
X.push_back(-(K + 1));
Y.push_back(-(K + 2));
C[i] = -K;
K++;
X.push_back(0);
Y.push_back(-(K - 1));
K++;
X.push_back(0);
Y.push_back(0);
}
if (all_cnt[i] == 4) {
K++;
X.push_back(-(K + 1));
Y.push_back(-(K + 2));
C[i] = -K;
K++;
X.push_back(0);
Y.push_back(0);
K++;
X.push_back(0);
Y.push_back(0);
}
}
for (int i = 0; i < N; i++) {
cur_cnt[A[i]]++;
int nxt = (i + 1 < N ? A[i + 1] : 0);
if (all_cnt[A[i]] == 1) {
C[A[i]] = nxt;
}
if (all_cnt[A[i]] == 2) {
if (cur_cnt[A[i]] == 1) {
X[-C[A[i]] - 1] = nxt;
}
else {
Y[-C[A[i]] - 1] = nxt;
}
}
if (all_cnt[A[i]] == 3) {
if (cur_cnt[A[i]] == 1) {
X[-C[A[i]] + 1 - 1] = nxt;
}
if (cur_cnt[A[i]] == 2) {
X[-C[A[i]] + 2 - 1] = nxt;
}
if (cur_cnt[A[i]] == 3) {
Y[-C[A[i]] + 2 - 1] = nxt;
}
}
if (all_cnt[A[i]] == 4) {
if (cur_cnt[A[i]] == 1) {
X[-C[A[i]] + 1 - 1] = nxt;
}
if (cur_cnt[A[i]] == 2) {
X[-C[A[i]] + 2 - 1] = nxt;
}
if (cur_cnt[A[i]] == 3) {
Y[-C[A[i]] + 1 - 1] = nxt;
}
if (cur_cnt[A[i]] == 4) {
Y[-C[A[i]] + 2 - 1] = nxt;
}
}
}
answer(C, X, Y);
return;
}
K = 0;
while ((1 << K) < N) {
K++;
}
C.resize(M + 1, -1);
C[0] = A[0];
if (K == 0) {
answer(C, X, Y);
return;
}
X.resize((1 << K) - 1);
Y.resize((1 << K) - 1);
build(1, 0, 0);
answer(C, X, Y);
}
