#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;
//}
int inf = 1 << 30;
std::vector <std::pair <int, int>> sw;
std::vector <int> c, x, y;
std::vector <int> dir;
void place(int node, int to_place) {
//std::cerr << "<" << node << ", " << to_place << ">" << std::endl;
int tir = dir[node];
dir[node] ^= 1;
if (tir == 0) {
//left
if (sw[node].first == inf) {
sw[node].first = to_place;
return;
}
//std::cerr << sw[node].first << std::endl;
assert(sw[node].first <= 0);
place(-sw[node].first, to_place);
return;
} else {
//right
if (sw[node].second == inf) {
sw[node].second = to_place;
return;
}
assert(sw[node].second <= 0);
place(-sw[node].second, to_place);
return;
}
assert(false);
}
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::vector <int> layer;
for (int i = 0; i < ((n + 1) >> 1); i++) {
sw.emplace_back(inf, inf * (i == ((n + 1) >> 1) - 1 ? -1 : 1));
layer.push_back(i);
}
for (int i = 0; i < depth - 1; i++) {
//std::cerr << "layer: ";
//for (int j : layer) std::cerr << j << " ";
//std::cerr << std::endl;
std::vector <int> new_layer;
for (int j = 0; j < (int)layer.size(); j += 2) {
new_layer.push_back(sw.size());
sw.emplace_back(-layer[j],
j + 1 < (int)layer.size() ? -layer[j + 1] : -inf);
}
std::swap(layer, new_layer);
}
assert((int)layer.size() == 1);
for (auto& p : sw) std::swap(p.first, p.second);
int first = layer[0];
//std::cerr << "first: " << first << std::endl;
for (auto& p : sw) {
if (p.first == -inf) {
p.first = -first;
}
if (p.second == -inf) {
p.second = -first;
}
}
//for (auto p : sw) std::cerr << "(" << p.first << ", " << p.second << ")" << std::endl;
c.resize(m + 1, -first);
c[0] = a[0]; // this is 1 idx
a.push_back(0);
dir.resize(sw.size(), 0);
for (int i = 1; i < (int)a.size(); i++) {
//std::cerr << "palce idx = " << i << " (" << a[i] << ")" << std::endl;
place(first, a[i] /* this is 1 idx */);
}
for (int& i : c) if (i <= 0) i--; // make 1 idx
for (auto p : sw) {
//std::cerr << "p: (" << p.first << ", " << p.second << ")" << std::endl;
x.push_back(p.first -(p.first < 0));
y.push_back(p.second -(p.second < 0));
}
answer(c, x, y);
}
//int main() {
//std::vector <int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
//int m = 11;
//create_circuit(m, a);
//}
