Routing#1258

Routing

1 Sekunde

128 Megabyte

Leicht

You work as an engineer for the Inane Collaboration for Performance Computing, where you are in charge of designing an intercommunication network for their computers. The network is arranged as a rectangular array of $2 n - 1$ 2n - 1 rows, each having $2^{n - 1}$ 2^{n-1} switches. A switch is a device with two input wires, $X$ and $Y$ , and two output wires, $X^{'}$ X' and $Y^{'}$ Y'. If the switch is off, data from input $X$ will be relayed to output $X^{'}$ X', and data from $Y$ to $Y^{'}$ Y'. If it is on, $X$ will be connected to $Y^{'}$ Y' and $Y$ to $X^{'}$ X'. Additionally, there are $2^{n}$ 2^n computers in the topmost and bottommost rows, and messages need to be sent between pairs of them. Data from two different sources cannot share a wire, but both pieces of data can be routed through the same switch on different inputs.

You have decided that the network that best suits your needs has the Benes topology. A $1$ -Benes network is just a switch. For $n > 1$ n > 1, an $n$ -Benes network can be constructed recursively as follows:

In the first (top) row there are $2^{n - 1}$ 2^{n-1} switches such that switch $j$ ( $0 \leq j < 2^{n - 1}$ 0 \leq j < 2^{n-1}) receives data inputs from computers $2 j$ and $2 j + 1$ 2j + 1 (we label the computers in the topmost and bottommost rows with integers between $0$ and $2^{n} - 1$ 2^n - 1 inclusive, from left to right).
A perfect shuffle permutation is applied to the output wires between the first and the second rows of switches. Output number $j$ in a row is connected to input number $j^{'}$ j' in the next row, where $j^{'}$ j' is obtained by rotating the $n$ -bit binary representation of $j$ one bit to the right (inputs and outputs are numbered from left to right).
If $n > 2$ n > 2, the next rows of switches, up to (and including) the last but one, form two $(n - 1)$ (n - 1)-Benes subnetworks, one on the left and the other on the right side.
The inverse shuffle permutation is then applied to the outputs, and a final row of switches is added.

For example, the figure above shows the Benes network for $n = 3$ n = 3 (squares represent switches; computers in the top and bottom rows are not drawn, but assigned with integers from $0$ to $7$ ). The figure shows a possible state of the switches. Squares where two lines cross indicate switches that have been turned on. This state allows simultaneous communication paths from computers $0$ , $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ at the bottom to $3$ , $7$ , $4$ , $0$ , $2$ , $6$ , $1$ , $5$ at the top, respectively.

You are given a set of pairs $(a, b)$ of computers to connect simultaneously (where $a$ is a computer in the bottom row and $b$ is a computer in the top row), and this must be done by means of wire-disjoint paths. You must determine the state of all switches so that this can be accomplished.

Eingabe

The first line of each test case is an integer $n$ ( $1 \leq n \leq 13$ 1 \leq n \leq 13), meaning there are $2^{n}$ 2^n pairs of computers to connect, as described above. A line with $n = 0$ n = 0 marks the end of the input and should not be processed.

Each line with $n > 0$ n > 0 is followed by another line containing $2^{n}$ 2^n integers. The $i$ -th integer ( $0 \leq i < 2^{n}$ 0 \leq i < 2^n) is the computer in the topmost row that the $i$ -th computer in the bottommost row must communicate with.

Ausgabe

For each case, the output should consist of $2 n - 1$ 2n - 1 lines, each containing a binary string of length $2^{n - 1}$ 2^{n-1}, indicating, for each switch, whether it must be turned on ( $1$ ) or off ( $0$ ).

The input is guaranteed to have at least one solution. If there are multiple solutions, print the lexicographically smallest one. That is, the top row string should be lexicographically smallest; in case of a tie, the second row should be lexicographically smallest, and so on.

Outputs for different test cases should be separated by a blank line.

Beispiele

Beispiel 1