Tiling the Shower Floor (Large)

Mingyu reports to the training center today. After the ceremonies he goes back to the barracks to rest, but the instructor calls him out and asks whether he knows Junseo. Junseo tiled the shower floor and covered the spot where the drain has to go, so Mingyu, who went to the same school, has to lay the floor again.

The shower floor is a square whose side length is a power of two. Junseo filled the whole floor with $2 \times 2$ tiles, and that leaves no way to keep the drain cell empty. An L shaped tile that covers three cells does work: it can cover every cell except the single drain cell. The L tile is a $2 \times 2$ square with one cell removed, and you may rotate it in any of the four directions.

Find a placement that covers every cell except the drain cell with L tiles that do not overlap.

The first line contains a natural number $K$ $(1 \le K \le 7)$ that fixes the size of the floor. The side length of the floor is $2^K$.

The second line contains two natural numbers $x$ and $y$ $(1 \le x, y \le 2^K)$, separated by a space, giving the position of the drain. The bottom left cell is $(1, 1)$ and the top right cell is $(2^K, 2^K)$.

Print the layout of the floor on $2^K$ lines. The first line is the row with $y = 2^K$ and the last line is the row with $y = 1$. On each line print the cells from $x = 1$ to $x = 2^K$, separated by single spaces. Print $-1$ for the drain cell and the number of the covering tile for every other cell.

Many placements exist, so the following rule picks one answer. Only a layout that follows this rule exactly is accepted.

Place the tiles by this recursive rule.

• A square of side length $1$ holds only the drain cell, so no tile is placed there.
• Split a square of side length $2^k$ $(k \ge 1)$ into four quadrants of side length $2^{k-1}$. Each quadrant has exactly one cell that touches the center of the square. Cover with a single L tile the three such cells that belong to the three quadrants without the drain. Then treat each of those three cells as the drain of its own quadrant and apply the same rule to all four quadrants.

Number the tiles after the placement is finished. Scan the rows in increasing order of $y$, and within a row scan the cells in increasing order of $x$. Each time you meet a tile that has no number yet, give it the next number: $1$, $2$, $3$, and so on.

For $1 \le K \le 7$ such a placement always exists, and no tile number exceeds $19000$.