1078 - 选数字V1
Description

从1-n中选出m个数,要求同样的数字不能重复选择,按照字典序正序输出所有方案。

例如:从1到4中选出2个数,共有6种方法,按照字典序输出,依次为:

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


Input
输入共2个数m, n,中间用空格分隔。(1 <= m <= n <= 20)


Output
按照字典序正序输出所有方案。


Examples

Input

4 2

Output

1 2
1 3
1 4
2 3
2 4
3 4
Hint
12% 2 <= n <= 5 1 <= m <= 5
56% 2 <= n <= 15 2 <= m <= 5
100% 2 <= n <= 20 2 <= m <= 17
样例解释
从1到4中选出2个数,共有6种方法,按照字典序输出,依次为:
1 2
1 3
1 4
2 3
2 4
3 4 
本题的递归并不只有这 1 种解法,还可以转换思路:
初始问题为:在 1−n 中选择  m  个数。因此对于 1−n 中的每一个数,我有选或不选 2 种情况。
用 F(cur,sel) ,表示当前要处理 cur 这个数,并且还需要选择 sel 个数的情况。
如果选择了当前的数,则递归处理 F(cur+1,sel−1) 。
如果没选当前的数,则递归处理 F(cur+1,sel) 。
递归的终止条件为 sel=0 或 cur>n ,此时输出所有已经选择的数。


题目参数
Time Limit 3 seconds
Memory Limit 128 MB
提交次数 78
通过次数 41