#include "doll.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
#include<unordered_map>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
void print(vi &L) {
cerr << "{";
for (auto i : L) cerr << i << ", ";
cerr << "}" << endl;
}
vi X, Y;
int oi(int a) {
return -a-1;
}
int oink(int s, int k, int d) {
//cerr << "oink(" << s << ", " << k << ", " << d << ")" << endl;
int p = X.size();
if (k <= 0) return s;
if (d <= 1) {
if (k == 1) return 0;
X.push_back(0);
Y.push_back(0);
return oi(p);
}
X.push_back(0);
Y.push_back(0);
int a = pow(2, (int)log2(k));
if (a >= k) a /= 2;
//cerr << "a : " << a << endl;
Y[p] = oink(s, a, d-1);
X[p] = oink(s, k-a, d-1);
return oi(p);
}
void oinkoink(vi &L, vi &K, int p, int pl, int s) {
/*
cerr << "oinkoink(..." << p << ", " << pl << ", " << s << ")" << endl;
print(L);
print(K);
print(X);
print(Y);
//*/
if (pl >= L.size()) return;
if (K[oi(p)]) {
K[oi(p)] = 0;
if (Y[oi(p)] == 0) {
Y[oi(p)] = L[pl];
oinkoink(L, K, s, pl+1, s);
return;
}
oinkoink(L, K, Y[oi(p)], pl, s);
return;
}
K[oi(p)] = 1;
if (X[oi(p)] == 0) {
X[oi(p)] = L[pl];
oinkoink(L, K, s, pl+1, s);
return;
}
oinkoink(L, K, X[oi(p)], pl, s);
}
void create_circuit(int m, vector<int> A) {
int n = A.size();
A.push_back(0);
vi C(m + 1, 0);
X.clear(); Y.clear();
vvi L(m+1);
L[0] = {A[0]};
for (int i = 0; i < n; i++) {
L[A[i]].push_back(A[i+1]);
}
int l = 0;
for (int i = 0; i < m+1; i++) {
/*
cerr << "iteration : " << i << endl;
cerr << "C : ";
print(C);
cerr << "X : ";
print(X);
cerr << "Y : ";
print(Y);
//*/
if (L[i].size() == 0) continue;
if (L[i].size() == 1) {
C[i] = L[i][0];
continue;
}
int a = (int)log2(L[i].size());
int b = pow(2, a);
if (b == L[i].size()) {
b /= 2;
a--;
}
X.push_back(-1);
Y.push_back(-1);
int p = X.size()-1;
C[i] = oi(p);
X[p] = oink(oi(p), L[i].size()-b, a+1);
Y[p] = oink(oi(p), b, a+1);
vi K(X.size(), 0);
oinkoink(L[i], K, oi(p), 0, oi(p));
}
/*
cerr << "C : ";
print(C);
cerr << "X : ";
print(X);
cerr << "Y : ";
print(Y);
//*/
answer(C, X, Y);
}
