#include "doll.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 200000, M = 100000, N_ = 1 << 18; /* N_ = pow2(ceil(log2(N))) */
int tmp[N_];
void split(int *aa, int n) {
int i, j, k;
for (i = 0, j = n / 2, k = 0; k < n; k++)
tmp[k % 2 == 0 ? i++ : j++] = aa[k];
memcpy(aa, tmp, n * sizeof *tmp);
}
vi xx(N * 2), yy(N * 2); int k;
int build(int *aa, int n) {
int u = k++;
if (n == 2)
xx[u] = aa[0], yy[u] = aa[1];
else {
split(aa, n);
xx[u] = -(build(aa, n / 2) + 1), yy[u] = -(build(aa + n / 2, n / 2) + 1);
}
return u;
}
int kk[M + 1], iii[M + 1][3], aa[N_], aa1[N];
void create_circuit(int m, vi aa_) {
vi cc(m + 1);
int n = aa_.size(), n_, n1, i, j;
for (i = 0; i < n; i++)
if (kk[aa_[i]] <= 2)
iii[aa_[i]][kk[aa_[i]]++] = i;
n1 = 0;
for (i = 0; i < n; i++)
if (kk[aa_[i]] > 2)
aa1[n1++] = i == n - 1 ? 0 : aa_[i + 1];
if (n1 != 0) {
n_ = 1;
while (n_ < n1)
n_ <<= 1;
for (i = 0; i < n_ - n1; i++)
aa[i] = -1;
for (i = 0; i < n1; i++)
aa[n_ - n1 + i] = aa1[i];
build(aa, n_);
for (j = 0; j <= m; j++)
cc[j] = -1;
}
cc[0] = aa_[0];
for (j = 0; j <= m; j++)
if (kk[j] == 1) {
i = iii[j][0];
cc[j] = i + 1 == n ? 0 : aa_[i + 1];
} else if (kk[j] == 2) {
int u, i1, i2;
i1 = iii[j][0], i2 = iii[j][1];
cc[j] = -((u = k++) + 1);
xx[u] = i1 + 1 == n ? 0 : aa_[i1 + 1], yy[u] = i2 + 1 == n ? 0 : aa_[i2 + 1];
}
xx.resize(k), yy.resize(k);
answer(cc, xx, yy);
}
