Description

There are $2^n \times 2^n$ cheaters $(n \le 10)$ standing in a square matrix, waiting for kkksc03's decision. kkksc03 decides to pardon some of them. He splits the square matrix evenly into $4$ smaller square matrices, and each smaller matrix has side length half of the original matrix. All cheaters in the upper-left matrix will be pardoned. In the remaining $3$ smaller matrices, each matrix is split into $4$ even smaller matrices, and cheaters are pardoned in the same way... until the matrix can no longer be split.

All cheaters who are not pardoned will receive the brown-name penalty.

Given $n$, output the fate of each cheater, where $0$ means pardoned and $1$ means not pardoned.

Input Format

An integer $n$.

Output Format

A $2^n \times 2^n$ 01 matrix representing whether each person is pardoned. There is one space between numbers.

3

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

Hint

Translated by ChatGPT 5