This is a communication problem.
There are two players: Player A (Isabel) and Player B (Tara). The jury will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information or receive information from the jury, but they may agree on the strategy they will use to communicate.
Isabel wants to send Tara a binary string $$$b$$$, which has size $$$n$$$. She can send information using a complete binary tree of exactly $$$2^h-1$$$ nodes, where $$$h$$$ is a given positive integer that represents the height of the tree. The nodes have been labelled with integers from $$$1$$$ to $$$2^h-1$$$, such that node $$$1$$$ is the root, and for any non-leaf node $$$v$$$ its left child is node $$$2v$$$ and its right child is node $$$2v+1$$$.
Isabel writes a binary value (0 or 1) on each node of the tree. After she writes a value on each node, she sends the final tree to Tara.
However, Lord Verity (their nemesis), will try to ruin their communication attempt. After Isabel sets the value of each node, Lord Verity will perform the following actions in the order they are listed, exactly once:
1. He chooses some node $$$u$$$.
2. He flips the value that Isabel wrote on node $$$u$$$. Specifically, if Isabel wrote 0 on node $$$u$$$, he flips it to 1, and vice versa.
3. If node $$$u$$$ is a leaf, he does nothing else. Otherwise, he swaps node $$$u$$$'s child pointers. Specifically, $$$u$$$'s left child becomes its right and $$$u$$$'s right child becomes its left simultaneously. Then, all nodes are re-labelled such that node $$$1$$$ is the root and for any non-leaf node $$$v$$$, its left child has label $$$2v$$$ and its right child has label $$$2v+1$$$.
Note that Lord Verity's actions may be adaptive. This means that the node he chooses to mess with is not fixed at the start, and may depend on what Isabel writes on her tree.
After Lord Verity messes with the tree, Tara will receive the structure of the new binary tree, and the value written on each node. She does not know which node Lord Verity has messed with. Formally, she receives a new binary string $$$l$$$, where $$$l_u$$$ is the value written on node $$$u$$$ after all nodes were re-labelled.
Her task is to compute the original string $$$b$$$.
There are only two possible combinations of $$$n$$$ and $$$h$$$:
The first combination will only be tested in the examples, for which a correct strategy is provided.
Your code will be ran exactly two times on each test. On the first run, you will be Isabel, and on the second Tara.
First Run Input
The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Isabel.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1024$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$h$$$ ($$$n = 1$$$ and $$$h = 2$$$, or $$$n = 2030$$$ and $$$h = 11$$$) – the size of the string $$$b$$$ and the height of the binary tree respectively. Note that the combination $$$n = 1$$$ and $$$h = 2$$$ only appears in the examples, and not in the main tests.
The next line contains a single binary string of size $$$n$$$, representing $$$b$$$.
Second Run Input
The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Tara.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1024$$$). The description of the test cases follows. Note that this number is equal to $$$t$$$ from the first run input.
The first line of each test case contains exactly two integers $$$n$$$ and $$$h$$$ — the size of the binary string $$$b$$$ and the height of the corresponding tree. The test cases may appear in a different order than in the first run.
The second line of each test case contains a binary string of length $$$2^h-1$$$, whose characters are $$$l_1, l_2, \ldots, l_{2^h-1}$$$. Here, $$$l_i$$$ represents the value of the node with label $$$i$$$, which is determined according to both Isabel's and Lord Verity's actions.
Note that after Lord Verity's actions, the labels will differ from the labels Isabel used.
Hacks
To make hacks, use the following format.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1024$$$) — the number of test cases.
The first line of each test case contains three integers $$$n$$$, $$$h$$$ and $$$p$$$ ($$$n = 2030$$$, $$$h = 11$$$, $$$1 \le p \le 2^h-1$$$) — the size of the string $$$b$$$, the height of the tree, and the label of the node Lord Verity chooses. The label $$$p$$$ refers to the labelling of the tree as Isabel wrote it, before Lord Verity's actions.
The second line of each test case contains a binary string $$$b$$$ of size $$$n$$$ — the string Isabel has to send.
Note that in hacks Lord Verity is not adaptive: he always chooses node $$$p$$$, regardless of what Isabel writes.
First Run Output
For each test case, output a binary string of length $$$2^h-1$$$, where the $$$i$$$-th character represents the value Isabel sets for node with label $$$i$$$.
Second Run Output
For each test case, output a binary string of size $$$n$$$, which is Tara's guess as to what $$$b$$$ is equal to.
first 2 1 2 0 1 2 1
000 101
second 2 1 2 010 1 2 001
1 0
When $$$n=1$$$, a correct strategy is the following.
Isabel wants to send $$$1$$$ bit but she has $$$2^h-1=2^2-1=3$$$ nodes available. Since Lord Verity only flips the value written on a single node, a correct strategy is to write the same value $$$b_1$$$ on all nodes of the tree. Then, Tara outputs the most frequent value that appears in $$$l$$$.
Take a look at the examples. Note that the order the test cases appear in the first run is not necessarily the same as the order they appear in the second run. Here, the two test cases have been swapped.
Isabel and Tara use the aforementioned strategy only for the case $$$b = 0$$$: Isabel writes the value $$$0$$$ on all nodes of the tree, so she outputs $$$000$$$. Then, Lord Verity uses his operation on node with label $$$3$$$ and Tara receives $$$l = 001$$$. Since $$$0$$$ is the most frequent value in $$$l$$$, she outputs $$$0$$$.
The other case where $$$b = 1$$$ is used only to show how Lord Verity's action affects the tree. Specifically, Isabel chooses to write the value $$$0$$$ on node $$$2$$$ and the value $$$1$$$ on nodes $$$1$$$ and $$$3$$$. Then, Lord Verity chooses to use his operation on node $$$1$$$. First, the value written on node $$$1$$$ becomes $$$0$$$. Then, its two children are swapped, and they are re-labelled: node $$$2$$$ gets label $$$3$$$ and node $$$3$$$ gets label $$$2$$$. Therefore we get $$$l = 010$$$. Magically, Tara can correctly determine that $$$b = 1$$$.
IMPORTANT NOTE: In these examples, Lord Verity chose to operate on nodes $$$1$$$ and $$$3$$$. However, when your code runs on the examples, it is not guaranteed that Lord Verity chooses the same nodes, and therefore using the same output as the examples is not guaranteed to be correct.
