题目描述

现有一个 $2^n \times 2^n（1\le n\le 10）$ 的正方形数字方阵，初始状态下，每一个像素都是 $0$ 。

将数字方阵等分为 4 个更小的正方形方阵，每个更小的方阵的边长是原来方阵的一半。其中右上角的那个方阵被命令保持为 $0$ ，剩下 3 个方阵中，每一个方阵继续分为 4 个更小的方阵，然后通过同样的方式进行操作......直到方阵无法再分下去为止。所有没有被命令保持为 $0$ 的像素都将被命令改为 $1$ 。

输入 $n$ ，请输出数字方阵的最终形态。

输入描述

一个整数 $n$ 。

输出描述

$2^n \times 2^n$ 的 $0-1$ 数字方阵，数字之间用一个空格隔开。

输入输出样例

输入 #1

3

输出 #1

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