#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void dbg(vector<int> x) {
cout << "DBG: ";
for (auto xx: x) cout << xx << " ";
cout << "\n";
}
int n, m;
vector<int> conn, x, y;
vector<pair<int, int>> tree;
vector<int> val, lab;
vector<bool> flip, ok;
int added = -1;
int build(int need) {
if (need == 1) return -1;
added++;
int node = added;
int toL = build((need + 1) / 2);
int toR = build((need + 1) / 2);
tree[node] = {toL, toR};
val[node] = need;
return node;
}
void get_special(int node) {
if (node == -1 || ok[node]) return;
if (val[node] % 2) {
int curr = tree[node].first;
while (tree[curr].second != -1) {
curr = tree[curr].second;
}
tree[curr].second = node;
}
ok[node] = true;
get_special(tree[node].first);
get_special(tree[node].second);
}
pair<int, int> get_leaf(int node) {
if (tree[node].first == -1 || tree[node].second == -1) {
if (!flip[node]) {
if (tree[node].first != -1) {
flip[node] = !flip[node];
return get_leaf(tree[node].first);
}
}
else {
if (tree[node].second != -1) {
flip[node] = !flip[node];
return get_leaf(tree[node].second);
}
}
flip[node] = !flip[node];
return {node, !flip[node]};
}
if (!flip[node]) {
flip[node] = true;
return get_leaf(tree[node].first);
}
else {
flip[node] = false;
return get_leaf(tree[node].second);
}
}
void assign_labs(int node) {
if (node == -1 || ok[node]) return;
ok[node] = true;
assign_labs(tree[node].first);
assign_labs(tree[node].second);
lab[node] = -x.size()-1;
x.push_back(-1);
y.push_back(-1);
}
void add_edges(int node) {
if (node == -1 || ok[node]) return;
ok[node] = true;
if (tree[node].first != -1) x[-lab[node]-1] = lab[tree[node].first];
if (tree[node].second != -1) y[-lab[node]-1] = lab[tree[node].second];
add_edges(tree[node].first);
add_edges(tree[node].second);
}
int build_tree(vector<int> vals, int f) {
int tot = vals.size();
tree.clear();
val.clear();
tree.resize(10*tot);
val.resize(10*tot);
ok.assign(10*tot, false);
added = -1;
build(tot);
get_special(0);
vector<pair<int, int>> ord;
flip.assign(10*tot, false);
while (ord.size() != vals.size()) {
ord.push_back(get_leaf(0));
}
lab.assign(10*tot, 0);
ok.assign(10*tot, false);
assign_labs(0);
ok.assign(10*tot, false);
add_edges(0);
for (int i = 0; i < tot; i++) {
if (ord[i].second == false) {
x[-lab[ord[i].first]-1] = vals[i];
}
else {
y[-lab[ord[i].first]-1] = vals[i];
}
}
return lab[0];
}
void create_circuit(int M, std::vector<int> A) {
m = M;
vector<int> a = A;
n = a.size();
conn.resize(m+1);
vector<vector<int>> aft(m+1);
for (int i = 0; i < n-1; i++) {
aft[a[i]].push_back(a[i+1]);
}
aft[a.back()].push_back(0);
aft[0].push_back(a[0]);
for (int i = 0; i <= m; i++) {
if (aft[i].empty()) {
conn[i] = i;
continue;
}
else if (aft[i].size() == 1) {
conn[i] = aft[i][0];
continue;
}
conn[i] = build_tree(aft[i], i);
}
dbg(x);
dbg(y);
answer(conn, x, y);
}
/*
int main() {
int m, n; cin >> m >> n;
vector<int> a;
for (int i = 0; i < n; i++) {
int x; cin >> x;
a.push_back(x);
}
create_circuit(m, a);
}*/
