#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)x.size())
void answer(vector<int> C, vector<int> X, vector<int> Y);
const int K = 1000*1000;
int n, m;
vector<int> a;
vector<vector<int>> adj;
int p = 0;
vector<int> c, x, y;
int new_switch(int g, int d) {
p++;
x.push_back(g);
y.push_back(d);
return -p;
}
int new_switch(int g) {
p++;
x.push_back(-p);
y.push_back(g);
return -p;
}
struct node {
int g, d, st, val;
};
vector<node> tree;
int newNode(int a = 0, int b = 0) {
tree.push_back({a, b, 0, -1});
return sz(tree)-1;
}
int buildTree(int t) {
if(sz(adj[t]) == 2)
return newNode(-2, -2);
vector<int> nodes;
int pr = 1;
while(pr < sz(adj[t])) pr *= 2;
for(int i = 0; i < pr / 4; ++i) nodes.push_back(newNode(-2, -2));
vector<int> sh;
for(int i = 0; i < sz(adj[t])/2-pr/4; ++i)
sh.push_back(newNode(-2, -2));
if(sz(adj[t])%2 == 1) sh.push_back(newNode(-K-K, -2));
while(sz(sh) < pr / 4) sh.push_back(newNode(-K-K, -K-K));
reverse(sh.begin(), sh.end());
for(auto i : sh) nodes.push_back(i);
if(sz(adj[t]) % 2 == 1)
tree[nodes.back()].d = -2;
vector<int> oldNodes;
while(sz(nodes) > 1) {
oldNodes = nodes;
nodes.clear();
for(int i = 0; i < sz(oldNodes); i += 2) {
int u = oldNodes[i], v = oldNodes[i + 1];
if(tree[v].g == -K-K && tree[v].d == -K-K) {
nodes.push_back(v);
continue;
}
if(tree[u].g == -K-K && tree[u].d == -K-K) {
nodes.push_back(newNode(-K-K, v));
continue;
}
nodes.push_back(newNode(u, v));
}
}
return nodes[0];
}
void printTree(int u) {
if(u < 0) {
// cout << u;
if(u == -K-K) cout << -1;
// u=-3-x, -u=3+x, x=-u-3
else cout << -u-K;
return;
}
cout << "(";
printTree(tree[u].g);
cout << ")";
cout << u;
cout << "(";
printTree(tree[u].d);
cout << ")";
}
int Cnt = 0;
int Root = 0;
void parcourir(int u, int t) {
if(Cnt == sz(adj[t])) return;
if(tree[u].st == 0) {
tree[u].st = 1;
if(tree[u].g < 0) {
if(tree[u].g != -K-K)
tree[u].g = -K-adj[t][Cnt++];
parcourir(Root, t);
}
else parcourir(tree[u].g, t);
}
else {
tree[u].st = 0;
if(tree[u].d < 0) {
if(tree[u].d != -K-K)
tree[u].d = -K-adj[t][Cnt++];
parcourir(Root, t);
}
else parcourir(tree[u].d, t);
}
}
int MOM = -1;
int construire(int u) {
if(u < 0) {
if(u == -K-K) return MOM;
if(u > -K) return u;
return -K-u;
}
if(u == Root) {
MOM = new_switch(0, 0);
int g = construire(tree[u].g);
int d = construire(tree[u].d);
x[-MOM-1] = g;
y[-MOM-1] = d;
return MOM;
}
int g = construire(tree[u].g);
int d = construire(tree[u].d);
return new_switch(g, d);
}
int create(int t) {
if(sz(adj[t]) == 0) return 0;
if(sz(adj[t]) == 1) return adj[t][0];
int root = buildTree(t);
// printTree(root);
// cout << endl;
Cnt = 0;
Root = root;
parcourir(root, t);
// printTree(root);
// cout << endl;
return construire(root);
}
vector<int> liste;
int PR = 1;
int mom = -1;
int build(int X, int pr) {
if(pr == 1) {
mom = new_switch(0, 0);
int g = build(X, 2 * pr);
int d = build(X + pr, 2 * pr);
x[-mom-1] = g;
y[-mom-1] = d;
return mom;
}
if(pr == PR) return (liste[X] == -1 ? mom : liste[X]);
int g = build(X, 2 * pr);
int d = build(X + pr, 2 * pr);
return new_switch(g, d);
}
int Create(int t) {
if(sz(adj[t]) == 0) return 0;
if(sz(adj[t]) == 1) return adj[t][0];
int pr = 1;
while(pr < sz(adj[t])) pr *= 2;
PR = pr;
liste.assign(pr, -1);
for(int i = 0; i < pr - sz(adj[t]); ++i)
liste[i] = -1;
for(int i = pr - sz(adj[t]); i < pr; ++i)
liste[i] = adj[t][i - pr + sz(adj[t])];
return build(0, 1);
}
void create_circuit(int M, vector<int> A) {
n = (int)A.size();
m = M;
a = A;
c.assign(m + 1, 0);
adj.assign(m + 1, vector<int>());
for(int i = 0; i < n - 1; ++i)
adj[a[i]].push_back(a[i + 1]);
adj[0].push_back(a[0]);
adj[a.back()].push_back(0);
for(int i = 0; i <= m; ++i)
c[i] = create(i);
answer(c, x, y);
}
