圣比特堡政府正在为新年城市装饰准备一项技术要求。 州长认为，在主广场上应该有一串包含 $n$ 个灯泡的彩灯。这些灯泡会开启和关闭，以娱乐圣比特堡的居民。

首席设计师决定，彩灯每秒钟都会改变其外观。彩灯中的每个灯泡都有两种状态：开和关。每一秒钟，恰好有一个灯泡会改变其状态（从开变关，或从关变开）。此外，首席设计师希望彩灯的所有灯光组合以 $2^n$ 秒为周期重复。在 $2^n$ 秒的周期内，必须呈现出彩灯的所有 $2^n$ 种可能的组合。

然而，该市的总工程师指出，频繁地开关灯泡会导致它们发生故障。为了尽量减少灯泡故障的可能性，要求每个灯泡开启和关闭的次数大致相同。

因此，作为政府信息技术部门的首席程序员，你现在需要完成这项最终的技术要求：

• 你需要制定一个包含 $2^n$ 种灯光组合的计划 $a_0, a_1, \dots, a_{2^n-1}$，其中 $a_k$ 是一个由 $n$ 个 0 和 1 组成的序列，$a_k[i] = 1$ 表示组合 $a_k$ 中第 $i$ 个灯泡是开启的，$a_k[i] = 0$ 表示组合 $a_k$ 中第 $i$ 个灯泡是关闭的。
• 计划中的所有组合必须各不相同。
• 该计划将以循环方式运行，每秒钟在彩灯上呈现下一个组合，即在第 $t$ 秒呈现组合 $a_{t \pmod{2^n}}$。
• 相邻的组合必须恰好有一个灯泡的状态不同。组合 $a_{2^n-1}$ 和 $a_0$ 也必须恰好有一个灯泡的状态不同。
• 令 $c_i$ 表示灯泡 $i$ 在一个完整周期内状态改变的次数，包括从 $a_{2^n-1}$ 到 $a_0$ 的最后一次改变。那么对于任意 $i \neq j$，值 $c_i$ 和 $c_j$ 的差值不得超过 2。

开始工作吧！

输入格式

输入包含一个整数 $n$ ($1 \le n \le 17$)。

输出格式

输出 $2^n$ 行，每行包含 $n$ 个字符，表示计划中的组合序列。保证存在满足所有要求的计划。

样例

样例输入 1

3

样例输出 1

000
010
011
111
110
100
101
001

样例输入 2

4

样例输出 2

0000
0010
1010
1011
0011
0111
0110
0100
0101
0001
1001
1101
1111
1110
1100
1000

说明

在第一个样例测试中，$c_1 = c_2 = 2, c_3 = 4$。 在第二个样例测试中，$c_1 = c_2 = c_3 = c_4 = 4$。