实际问题
题号:NC25192
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

本题的出题人在实习(摸鱼)中遇到了一个非常有意思的问题,这个问题的核心即需要枚举组合

组合即数学上的“C”的概念,我们知道 C(x,y)=y!/x!/(y-x)!

如果我们想枚举 C(3,4),我们有:

    1 2 3

    1 2 4

    1 3 4
    2 3 4

这道题就是这个意思,当然为了简化输出,我们只要你给出按顺序的第 k 个组合即可,如 C(3,4)的第 3 个是:1 3 4

注意组合内部是无序的,但是我们希望得到一个递增顺序的结果,即结果是

1 3 4,而非诸如 1 4 3 之流。

输入描述:

首先是一个整数T,表示数据输入的组数,T<=10。

对于每组数据,一行三个数n,m,k:

欲求C(m,n)的第k个组合。保证n<=100000,m<=n,k<=1000000,k<=C(m,n)。

输出描述:

对应T行,每行即结果。
示例1

输入

复制
2
6 3 10
100 5 1000

输出

复制
1 5 6
1 2 3 14 99

说明

对于第一组的样例,按顺序的组合:
(1) 1 2 3
(2) 1 2 4
(3) 1 2 5
(4) 1 2 6
(5) 1 3 4
(6) 1 3 5
(7) 1 3 6
(8) 1 4 5
(9) 1 4 6
(10)1 5 6