题目描述

有n（2<=n<=9)个环，拆装这些环的规则：第一个环可以随意拆装，第二个只有在第一环已装上时可以拆装，第三个只有在第二个环已装上且第一个环已拆下时可以拆装，第i个环只有在第 i-1环已装上，且第i-2、第i-3、…，第1环都拆下时可以装拆。

现输入n，表示这n个已经装上的环，现在输出拆下这n个环的最简单过程。输出方法是每个状态用0、1来表示，0表示对应位置上的环已卸下，1表示对应位置上的环已装上，输出每拆装一个环时候的状态，初始状态也要输出。

例如输入n=2，则输出：

11

10

00

输入

输入n，1<=n<=9

输出

输出拆装时的每个状态

样例

2

11
10
00