L-Tromino Tiling

The country of L has a proud tradition: every barracks should be arranged in the shape of the national emblem, an L–shape. However, the command center (which by its very nature is unique) is exempt from this requirement. Given a board of size \(2^k \times 2^k\) with one cell missing (representing the command center), your task is to tile the remainder of the board completely with L–shaped trominoes. In each tiling step an L–shaped tile (covering exactly 3 cells) is placed in such a way that the board is eventually fully covered without overlaps.

Note: The missing cell is given by its row and column index (0–indexed). You may assume that a solution always exists. Although there are multiple valid tilings, you must output the tiling obtained by the following recursive strategy:

1. If the current sub–board is of size 1×1, return.
2. Divide the board into four quadrants. Determine which quadrant contains the missing cell.
   • Place one L–tromino at the center of the board covering the center cell of the three quadrants that do not contain the missing cell. All cells covered by the same tromino should be marked with the same positive integer tile id.
3. Recurse on each quadrant (each quadrant now has exactly one missing cell – either the original missing cell or the cell covered by the tromino placed in step 2) until the sub–board size is 1×1.

Output the final board. The missing cell should be printed as 0 and every tile cell with its corresponding tile id. Separate numbers in a row by a single space.

Input and output format details are provided below.

inputFormat

The first line of input contains an integer \(k\) (with \(1 \le k \le 10\)); the board size is \(2^k \times 2^k\). The second line contains two integers \(r\) and \(c\) (0–indexed) which specify the row and column of the missing cell (i.e. the command center).

outputFormat

Output \(2^k\) lines, each containing \(2^k\) integers separated by a single space. The missing cell must be output as 0, and every tromino tile cell should have a positive integer id. All cells covered by the same tromino must have the same id.

sample

1
0 0

0 1
1 1