#include "doll.h"
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
vector<int> r[100009], st, c, x, y, rx, ry;
vector<pair<int, pair<int, int> > > sq;
int sc = 0, rc = -1, ft;
int vsq(int n, int ts, int te, int t)
{
if (ts >= te)
return 0;
int md = (ts + te) / 2;
if (n <= md)
return vsq(n, ts, md, t * 2);
else
return vsq(n, md + 1, te, t * 2) + t;
}
int vsq(int n, int tn)
{
return vsq(n, 0, tn - 1, 1);
}
int csw(int n, int tn)
{
sc--;
int tsc = sc;
if (ft >= n / 2) {
ft -= n / 2;
x[-sc - 1] = -1;
rc += n / 2;
if (ft >= n / 2) {
ft -= n / 2;
y[-sc - 1] = -1;
rc += n / 2;
}
else {
if (n == 2) {
rc++;
sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 1)));
}
else
y[-tsc - 1] = csw(n / 2, tn);
}
return tsc;
}
if (n == 2) {
rc++;
sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 0)));
rc++;
sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 1)));
return sc;
}
int a = csw(n / 2, tn), b = csw(n / 2, tn);
x[-tsc - 1] = a; y[-tsc - 1] = b;
return tsc;
}
void create_circuit(int M, std::vector<int> A) {
A.push_back(0);
int N = A.size();
for (int i = 0; i < N - 1; i++)
r[A[i]].push_back(A[i + 1]);
for (int i = 0; i < N - 1; i++)
if (r[A[i]].size() > 1)
st.push_back(A[i + 1]);
int t = 1, rn = 0;
while (t < st.size()) {
rn += t; t *= 2;
}
int rp = t - st.size();
for (int i = 0; i < rn; i++) {
x.push_back(100009);
y.push_back(100009);
}
ft = rp;
if (N > 2 && st.size() > 0) {
csw(t, t);
sort(sq.begin(), sq.end());
for (int i = 0; i < sq.size(); i++) {
if (sq[i].second.second == 0)
x[sq[i].second.first] = st[i];
else
y[sq[i].second.first] = st[i];
}
}
c.push_back(A[0]);
for (int i = 1; i <= M; i++) {
if (r[i].size() == 0)
c.push_back(0);
else if (r[i].size() == 1)
c.push_back(r[i][0]);
else
c.push_back(-1);
}
for (int i = 0; i < x.size() && x[i] != 100009; i++)
rx.push_back(x[i]);
for (int i = 0; i < y.size() && y[i] != 100009; i++)
ry.push_back(y[i]);
answer(c, rx, ry);
}
