#include "doll.h"
#include <iostream>
using namespace std;
vector<int> X, Y;
vector<int> XX, YY;
vector<int> was;
vector<int> go[300200];
int S;
void rec(int pos, int val) {
if (was[pos] == 0) {
if (XX[pos] == 0) {
X[pos] = val;
XX[pos] = 1;
was[pos] ^= 1;
return;
}
else {
was[pos] ^= 1;
rec(-X[pos] - 1, val);
}
}
else {
if (YY[pos] == 0) {
YY[pos] = 1;
Y[pos] = val;
was[pos] ^= 1;
return;
}
else {
was[pos] ^= 1;
rec(-Y[pos] - 1, val);
}
}
}
void build(int v, int cur, int len) {
if (cur < len) {
XX[v] = 1;
YY[v] = 1;
S++;
X[v] = -S;
was.push_back(0);
X.push_back(0), Y.push_back(0);
XX.push_back(0), YY.push_back(0);
S++;
Y[v] = -S;
was.push_back(0);
X.push_back(0), Y.push_back(0);
XX.push_back(0), YY.push_back(0);
build(-X[v] - 1, cur + 1, len);
build(-Y[v] - 1, cur + 1, len);
}
else {
return;
}
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
vector<int> C(M + 1);
if (M == 1 && false) {
C[0] = +1;
C[1] = -1;
--N;
X.resize(N), Y.resize(N);
for (int k = 1; k <= N; ++k) {
if (k == 1)
X[k - 1] = 1;
else
X[k - 1] = 1 - k;
if (k == N)
Y[k - 1] = 0;
else
Y[k - 1] = -1 - k;
}
answer(C, X, Y);
return;
}
X.clear(), Y.clear();
A.push_back(0);
C[0] = A[0];
for (int i = 0; i < N; ++i) {
go[A[i]].push_back(A[i + 1]);
}
for (int i = 1; i <= M; ++i) {
if (go[i].size() == 0)
continue;
if (go[i].size() == 1) {
C[i] = go[i][0];
}
else {
int n = 1, len = 0;
while (n < go[i].size()) {
n <<= 1, len++;
}
S++;
was.push_back(0);
X.push_back(0), Y.push_back(0);
XX.push_back(0), YY.push_back(0);
C[i] = -S;
build(-C[i] - 1, 1, len);
for (int j = 0; j < go[i].size() - 1; ++j)
rec(-C[i] - 1, go[i][j]);
for (int j = go[i].size() - 1; j < n - 1; ++j)
rec(-C[i] - 1, C[i]);
rec(-C[i] - 1, go[i].back());
}
}
answer(C, X, Y);
}
