题目描述
我们都非常熟悉经典的爬楼梯问题了。对于" n 级台阶，每次可以走 1 级台阶或者 2 级台阶，一共有多少种方案到达第 n 级台阶"我们都非常熟悉了。

今天，张老师给大家出一个难题，要求大家把所有的方案打印出来。

输入格式
一行一个数 n

数据范围
1 <= n <= 15

输出格式
多行，每行一个由1或2构成的方案，数中间用空格隔开。
输出顺序按照字典序序从小到大。

样例

4

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2