该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

这是孵化器一轮考核第二期的D题，旨在考查大家对递归的应用能力

背景

月光林地的德鲁伊班纳，现在站在了装有月照护甲的宝箱面前。由于他在撬锁的巧手检定中掷出了大失败，他现在只好亲手破解守护这个宝箱的九连环。

经过他的不懈尝试，他终于发现了解开九连环的一些规律，请你编写程序找出能将所有环取下的操作顺序。

"为什么我没有学敲击术"班纳暗自懊恼。

题目描述

九连环是一个中国的传统玩具，它由一个环柄和套在上面的n个金属环组成。所有金属环有取下和在环柄上两种状态，分别用'0'和'1'表示。最开始所有的环都是在环柄上的状态，即都为'1'。对于每个金属环，改变他的状态需要满足以下规则：

1.第一个环在任意情况下均能任意改变状态。

2.第二个环仅在第一环状态为 '1' 时能够改变状态。

3.第n个环仅能在第n-1个环状态为'1'且第n-2环以及前面的所有环状态均为 '0' 时能够改变状态。(n>2)

你的目的就是找出将九连环初始状态'111111111'变成'000000000'的规律，规定最左边的数字是第一个环。

格式

Input

n，表示九连环环柄上金属环的个数

Output

用1表示金属环在环柄上，用0表示被取下，每行表示一个操作后所有环的状态。输出取下所有金属环的最简顺序。

Samples

4

1011
0011
0010
1010
1110
0110
0100
1100
1000
0000

Limitation

$1$s, $1024$KiB for each test case. n<$20$.