题目背景

一个军事演习场地被划分为 $2^n \times 2^n$ 的方格区域。

题目描述

演习场地是一个 $2^n \times 2^n (n \le 10)$ 的正方形网格，每个格子初始状态为危险（用 $1$ 表示）。

导演组决定划定安全区域：将当前网格均分为 $4$ 个等大的正方形子区域，其中左上角的子区域全部标记为安全（用 $0$ 表示），其余 $3$ 个子区域各自继续均分为 $4$ 份，对左上角标记安全……如此递归，直到子区域大小为 $1 \times 1$ 为止。

给出 $n$，请输出每个格子的最终状态：$0$ 表示安全，$1$ 表示危险。

输入格式

一个整数 $n$。

输出格式

$2^n \times 2^n$ 的 $01$ 矩阵，代表每个格子的状态。相邻数字之间用一个空格分隔。

样例

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