Cheater's Fate

In this problem, you are given an integer \(n\) (with \(n \le 10\)). There are \(2^n \times 2^n\) cheaters standing in a square formation waiting for kkksc03's judgment. kkksc03 decides to pardon some of them according to the following procedure:

Consider the square matrix of cheaters. If the matrix size is at least \(2 \times 2\) (i.e. \(n\geq 1\)), divide it evenly into 4 smaller square sub-matrices, each with side length half of the current matrix. The cheaters in the top-left sub-matrix are pardoned (output \(0\)); for the remaining three sub-matrices, the same process is applied recursively, i.e., each is divided into 4 even smaller squares and the cheaters in the top-left sub-matrix of each are pardoned. This process continues until the sub-matrices cannot be divided further (i.e. when the matrix is \(1 \times 1\)).

All cheaters that are not pardoned will be punished (output \(1\)).

Your task is to output the fate of each cheater as a \(2^n \times 2^n\) matrix, where a 0 indicates a pardoned cheater and a 1 indicates a punished cheater.

The key idea behind the solution is to simulate the recursive division. Initially, mark every cell as punished (1). Then, for every sub-matrix of size at least 2, mark its top-left quadrant (of size \(\frac{side}{2}\)) as pardoned (0) and recursively process the other three quadrants (top-right, bottom-left, bottom-right) if their size is greater than 1.

For example, when \(n=1\), the matrix is \(2 \times 2\) and only the cell in the top-left is pardoned:

[ \begin{bmatrix} 0 & 1 \ 1 & 1 \end{bmatrix} ]

inputFormat

The input consists of a single integer \(n\) \((0 \le n \le 10)\), representing that the cheaters form a \(2^n \times 2^n\) matrix.

outputFormat

Output \(2^n\) lines, each containing \(2^n\) integers (each either 0 or 1) separated by spaces. Each integer represents the fate of a cheater (0 for pardoned, 1 for punished).

sample

0

1