题目描述

长度为 $n$ 的格雷码是一个包含 $2^n$ 个元素的序列，序列的每一个元素都是长度为 $n$ 的二进制串，并且序列中任意两个连续的二进制串只相差一位，即它们的 Hamming 距离为 $1$。

你的任务是输出长度为 $n$ 的格雷码。

输入格式

输入一个正整数 $n$。

输出格式

输出 $2^n$ 行，每行都是长度为 $n$ 的二进制串，这 $2^n$ 行需要是一个有效的格雷码。

你可以输出任何有效的格雷码。

样例

2

00
01
11
10

数据范围

• $1 \le n \le 16$