407678: GYM102870 H Hamming Code and Orz Pandas

Chuan the Country Builder is a famous accordion artist. He planned to hold a concert in the Orz Panda's Land. Unfortunately he is just cured from a COVID-19 infection so he would be rejected by the Border Control Administration of the Orz Panda.

As an alternative, Chuan recorded his accordion songs as a binary data flow and sent the binary data to the Orz Pandas. However Chuan's enemy, Bai the Sleeper can use a magic to modify the binary data being transfered. To prevent Bai's disruption, Chuan used Hamming code to encode the binary data.

A data block using Hamming code $$$d$$$ has $$$2^k$$$ bits, numbered $$$0, 1, \cdots, 2^k - 1$$$. Let $$$f(x)$$$ be the number of ones in the binary form of the integer $$$x$$$, for example $$$f(10) = 2$$$ since $$$10 = 1010_2$$$. To use Hamming code, Chuan can only put data into those positions $$$x$$$ with $$$f(x) > 1$$$. If we name the bits at those postions "data bits", there are only $$$2^k - k - 1$$$ data bits.

For example, if $$$k = 4$$$, the size of $$$d$$$ will be $$$2^k = 16$$$, and there are $$$2^4 - 4 - 1 = 11$$$ data bits. If the data is $$$10110111011$$$, the original data block is like:

$$$$$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline d(i) & ? & ? & ? & 1 & ? & 0 & 1 & 1 & ? & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ \hline \end{array} $$$$$$

Then the remaining $$$k+1$$$ non-data bits (marked as $$$?$$$ above) should be filled. Firstly, for each position $$$j \in [0, k)$$$, the $$$2^j$$$-th bit is caluculated as the xor-sum:

$$$$$$d(2^j) = \bigoplus_{(i \cap 2^j) \neq 0, i \neq 2^j} d(i)$$$$$$

$$$\cap$$$ is the binary-and operator. For example, in the data block above we have:

$$$$$$d(2^0) = d(3) \oplus d(5) \oplus d(7) \oplus d(9) \oplus d(11) \oplus d(13) \oplus d(15) = 0$$$$$$ $$$$$$d(2^1) = d(3) \oplus d(6) \oplus d(7) \oplus d(10) \oplus d(11) \oplus d(14) \oplus d(15) = 1$$$$$$ $$$$$$d(2^2) = d(5) \oplus d(6) \oplus d(7) \oplus d(12) \oplus d(13) \oplus d(14) \oplus d(15) = 1$$$$$$ $$$$$$d(2^3) = d(9) \oplus d(10) \oplus d(11) \oplus d(12) \oplus d(13) \oplus d(14) \oplus d(15) = 1$$$$$$

Secondly, the $$$0$$$-th bit is calculated as the xor-sum:

$$$$$$d(0) = \bigoplus_{i > 0} d(i)$$$$$$

For example, in the data block above we have $$$d(0) = 1$$$. At last this data block shall become

$$$$$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{i} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline \text{d(i)} & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ \hline \end{array} $$$$$$

Then Chuan would transfer the encoded data block to the Orz Pandas. Bai will attempt to disrupt the data transfer, but he is too sleepy so he can only change at most $$$2$$$ bits in a block. It can be proved that the Orz Pandas can always detect if the block is disrupted by Bai. And it can be proved that if Bai only changed $$$1$$$ bit in a block, the Orz Pandas can find exactly the bit which is changed. You should write a program to implement it for the Orz Pandas.

There are multiple test cases, please process until EOF.

For each test case, the first line contains an integer $$$k$$$. The second line contains $$$2^k$$$ binary bits $$$d(0), d(1), \cdots, d(2^k-1)$$$.

It's guaranteed that $$$3 \leq k \leq 16$$$, $$$d(i) \in \{0, 1\}$$$, and at most $$$2$$$ bits are changed by Bai. The total number of binary bits in the input file will not exceed $$$1048576$$$.

You should take care that Bai may change non-data bits.

For each test case output one line. If the block is not disrupted, output "good". If the block is disrupted and $$$2$$$ bits are changed, output "broken". If the block is disrupted and only $$$1$$$ bit is changed, output "d(x) is changed", where "x" should be replaced by the position of the only changed bit.

4
1011101110111011
4
1011101110111010
4
1011101110111110

good
d(15) is changed
broken