题目背景

翻译自 CSES-2205 题。

题目描述

如果两个相邻的二进制数在二进制表示中恰好只有一位不同，则称为格雷码。你的任务是构建一个包含 $2^n$ 个 $n$ 位二进制串的格雷码列表。

输入格式

输入一个整数 $n$。

输出格式

输出 $2^n$ 行，每行一个 $n$ 位二进制串（可以以任意顺序，但任意两个相邻行必须恰好有一位不同，且首行必须是全零）。

样例

2

00
01
11
10

说明/提示

$1 \le n \le 16$。