格雷码 (Task 2205)

• 链接: https://cses.fi/problemset/task/2205
• 板块: Introductory Problems
• 时限: 1.00 s ｜ 内存: 512 MB

描述

格雷码是长度为 $n$ 的所有 $2^n$ 个位串的一个列表，其中任意两个相邻的字符串恰好只有一位不同（即它们的汉明距离为 1）。你的任务是为给定的长度 $n$ 构造一个格雷码。

输入

输入仅一行，包含一个整数 $n$。

输出

打印 $2^n$ 行，描述该格雷码。你可以打印任意一个合法解。

约束

• $1 \le n \le 16$

样例

输入：
2
输出：
00
01
11
10