题目描述

圣比茨堡政府正在准备新年城市装饰方案。广场上将有一串包含 $n$ 盏灯的彩灯，每盏灯有两种状态：亮或灭。

彩灯每秒改变一次外观。每次变化时，必须恰好有一盏灯改变状态，即从亮变灭，或从灭变亮。设计师希望所有可能的灯光组合以 $2^n$ 秒为周期循环出现，并且在一个周期内，所有 $2^n$ 种组合都恰好出现一次。

工程师指出，如果某些灯频繁开关，更容易损坏。因此要求每盏灯的状态变化次数尽量均衡。

你需要构造一个长度为 $2^n$ 的组合序列 $a_0,a_1,\ldots,a_{2^n-1}$。每个 $a_k$ 是长度为 $n$ 的 01 串，其中第 $i$ 位为 1 表示第 $i$ 盏灯亮，为 0 表示灭。要求：

1. 所有组合两两不同；
2. 相邻两个组合恰好一位不同；
3. 最后一个组合 $a_{2^n-1}$ 与第一个组合 $a_0$ 也恰好一位不同；
4. 设 $c_i$ 为第 $i$ 盏灯在完整周期内状态变化的次数，包括从 $a_{2^n-1}$ 回到 $a_0$ 的那次变化。对任意 $i \ne j$，$c_i$ 与 $c_j$ 的差不超过 $2$。

请输出任意满足条件的方案。

输入格式

输入一个整数 $n$。

输出格式

输出 $2^n$ 行，每行一个长度为 $n$ 的 01 串，表示一个满足要求的灯光组合序列。

保证一定存在满足条件的方案。

数据范围

$1 \le n \le 17$。

样例 1

输入：
3

输出：
000
010
011
111
110
100
101
001

样例 2

输入：
4

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

样例说明

第一个样例中，三盏灯的变化次数分别为 $2,2,4$。
第二个样例中，四盏灯的变化次数均为 $4$。