题目描述

小明的班级有 n 名学生，编号为 1～n，现在要选出一些人（数量不限），组成一个队伍参加比赛，一共有多少选择方法？要求输出每种方法选出的队伍。

例如有 4 个人，选出编号 1,2,4 这三个人组成一个队伍，就是一种选择方法。我们将整个班的学生称作一个集合，选出来的队伍就叫做子集。也可以一个人也不选，这样队伍中一个人都没有，我们把这种子集称作空集。

我们把编号 1～n 的学生看做整数 1～n。写一个递归函数，枚举 1～n 中取若干个数的每种方法（子集枚举），对每种方法把取出的数从小到大排序，若两种方法中前 k-1 个数的选取情况相同，则取了第 k 个数的在前。例如对 n=4，应该按如下顺序给出结果：

{1,2,3,4},{1,2,3},{1,2,4},{1,2},{1,3,4},{1,3},{1,4},{1},{2,3,4},{2,3},{2,4},{2},{3,4},{3},{4},{}。

输入格式

一个正整数 n。

输出格式

输出 2^n 行，每行一个子集，按题目要求顺序。

输入样例 #1

4

输出样例 #1

1 2 3 4
1 2 3
1 2 4
1 2
1 3 4
1 3
1 4
1
2 3 4
2 3
2 4
2
3 4
3
4

输入样例 #2

1

输出样例 #2

1

输入样例 #3

2

输出样例 #3

1 2
1
2

数据范围与约定

1 ≤ n ≤ 12