Problem G: 爬楼梯所有方案问题（动规课程A）（3.4）

Problem G: 爬楼梯所有方案问题（动规课程A）（3.4）

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 12Submit: 21Statistics

Description

你正在爬一个有n个台阶的楼梯，每次只能上1个或者2个台阶，那么到达顶端有多种不同的方法，请打印出所有方案。

Input

一行一个数n，范围[2..15]

Output

多行，每行一个由1或2构成的方案，数中间用空格隔开。

输出要求字典序序最小。


Sample Input Copy 

4

Sample Output Copy 

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2
Submit