1080 - 选数字 V3
Description

小明很喜欢选数字,现在小明得到 n 个数,他想得到从 n 个数里面选取 k个数的所有方案,由于小明的作业很多,现在没有时间解决这个问题,聪明的你可以帮助小明解决这个问题吗?

Input
输入包括两行数据,第一行包括两个数n(1<=n<25),k(1<=k<=min(n,19)),表示数列数的个数以及要从数列里面选取数的个数。
第二行n个数表示该数列的n个数(0<ai<=100,ai表示数列里面的数,ai可能有重复)。
(两个数之间用空格分开)。


Output
按字典序输出所有的方案(格式参照样例)


Examples

Input

4 2
1 1 2 3

Output

1 1
1 2
1 3
2 3
Hint
对于10%的数据,1 <= n <= 5, k<= n
对于50%的数据,1 <= n <= 10, k<= n
对于100%的数据,1 <= n <=24, k<= min(n,19)


	样例解释
从(1,1,2,3)4个数字里面选2个,有(1,1),(1,2),(1,3),(2,3)四种选法。

	为了保证输出的字典序,先对给出的数字进行排序,如果有相同的数字,那么排序后会挨在一起。

此时如果直接套用从 n 个数中选择 m 个数的递归,由于 ai 中有相同的数字,因此会出现完全重复的选择。

为了不出现重复的选择,我们规定如果挨着的两个数字相同,假如前一个没有选,后一个也不能选。

这样需要用一个 bool 数组记录选或未选的状态。剩下的逻辑就同 n 个数中选 m 个数一样了。按照之前的方法递归处理即可


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 64
通过次数 30