#include "doll.h"
#include <bits/stdc++.h>
//void answer(std::vector <int> c, std::vector <int> x, std::vector <int> y) {
//std::cerr << "answered" << std::endl;
//for (int i : c) std::cerr << i << " ";
//std::cout << std::endl;
//for (int i : x) std::cerr << i << " ";
//std::cout << std::endl;
//for (int i : y) std::cerr << i << " ";
//std::cout << std::endl;
//}
struct Switch {
int id;
int left, right;
int depth = 1;
bool dir = false; // false = left , true = right
};
std::vector <Switch> sw;
void make_tree(int node, int depth, int max_depth) {
if (depth == max_depth) return;
assert(depth < max_depth);
sw[node].left = (int)sw.size() + 1;
sw[node].right = (int)sw.size() + 2;
sw.push_back({ (int)sw.size() + 1, -1, -1, depth + 1 });
sw.push_back({ (int)sw.size() + 1, -1, -1, depth + 1 });
make_tree(sw[node].left - 1, depth + 1, max_depth);
make_tree(sw[node].right - 1, depth + 1, max_depth);
}
void find_exits(int node, int depth, int max_depth, int exit_number) {
if (depth == max_depth) {
if (sw[node].dir == false) {
sw[node].left = exit_number;
} else {
sw[node].right = exit_number;
}
sw[node].dir ^= 1;
return;
}
assert(depth < max_depth);
if (sw[node].dir == false) {
find_exits(sw[node].left - 1, depth + 1, max_depth, exit_number);
} else {
find_exits(sw[node].right - 1, depth + 1, max_depth, exit_number);
}
sw[node].dir ^= 1;
}
void create_circuit(int m, std::vector <int> a) {
int n = a.size();
int size = 1;
int depth = 0;
while (size < n) {
size <<= 1;
depth++;
}
//std::cerr << n << ": " << size << ", " << depth <<std::endl;
sw.push_back({ 1, -1, -1 });
make_tree(0, 1, depth);
int cnt = 0;
for (int i = 0; i < n - 1; i++) {
find_exits(0, 1, depth, a[i + 1]);
cnt++;
}
for (; cnt < size - 1; cnt++) {
find_exits(0, 1, depth, -1);
}
find_exits(0, 1, depth, 0);
std::vector <int> c(m + 1), x(sw.size()), y(sw.size());
c[0] = a[0];
for (int i = 1; i <= m; i++) {
c[i] = -1;
}
for (auto node : sw) {
if (node.depth != depth) {
x[node.id - 1] = -node.left;
y[node.id - 1] = -node.right;
} else {
x[node.id - 1] = node.left;
y[node.id - 1] = node.right;
}
}
//for (auto s : sw) {
//std::cerr << s.id << " " << s.left << ", " << s.right << " and "
//<< s.depth << " dir: " << s.dir << std::endl;
//}
answer(c, x, y);
}
//int main() {
//for (int i = 1; i <= 10; i++) {
//std::vector <int> a(i, 0);
//create_circuit(1, a);
//}
//std::vector <int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
//int m = 11;
//create_circuit(m, a);
//std::vector <int> a = { 1, 2, 1, 3 };
//int m = 4;
//create_circuit(m, a);
//}
