本题是选数 ( Easy )的困难版本，只有数据范围不同。

确保简单版本是困难版本的子集，即困难版本的代码一定能通过简单版本。

题目描述

小劉有 n 个数字为 1 ~ n ，现在他想从中挑出 k 个数字，把k个数字放成一排，请你帮助小劉求出所有可能排成的样子。

输入描述

每组测试数据描述如下：

第一行两个数字 n , k ( 1 <= n <= 8 ) ( 1 <= k <= 8)

输出描述

输出所有组合即可，每个组合占一行，不要求顺序。

样例

1 1

1

3 2

1 2
1 3
2 1
2 3
3 1
3 2