著名舞蹈表演的导演计划巡演。已经决定巡演将包括高达 $$$m$$$ 的音乐会。
剧团里有$$$n$$$个舞者。每个舞者都有其尴尬的特征:第 $$$i$$$ 个舞者的尴尬等于 $$$a_i$$$。
导演喜欢多样性。因此,每场音乐会都将由不同的舞者表演。一名舞者可以在多场音乐会上表演。例如,一组舞者可能在一场音乐会中表演,而这组舞者的子集可能在另一场音乐会中表演。唯一的限制是同一组舞者不能表演两次。
与舞者人数较少的场景相比,导演更喜欢舞者人数较多的场景。如果两套舞者人数相同,那么导演会优先选择舞者尴尬度较小的那一套。如果两组舞者的体型和笨拙程度相同,那么导演就不会偏向哪一组更好。
一项营销研究表明,如果音乐会中表演的所有舞者的总尴尬程度大于 $$$k$$$,则观众还没有准备好来观看音乐会。
导演想要找到$$$m$$$音乐会的最佳计划。他想写下所有可能的舞者组合;然后去掉总尴尬度大于 $$$k$$$ 的集合。剩下的几组舞者将根据他的喜好进行排序。最受青睐的一组舞者将举办第一场音乐会,第二首选的舞者组将举办第二场音乐会,依此类推,直到第 $$$m$$$ 场音乐会。如果有效组数总数小于$$$m$$$,则音乐会总数将等于有效组数。
原来导演把找方案的任务委托给你了!请注意,由于导演对具有相同尺寸和完全尴尬的舞者组没有偏好,因此可能有多个可接受的计划。在这种情况下,这些计划中的任何一个都足够好了。对于每场音乐会,找出舞者的数量以及表演现场的总体尴尬程度。另外,为最后一场音乐会找到它的舞者。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 输入中测试用例的数量。然后是测试用例。
每个测试用例都以包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ 的行开头 ($$$1 \le n \le 10^6$$$, $$$1 \le k \le 10^{18}$$$, $$$1 \le m \le 10^6$$$) — 舞者总数,最大可接受的尴尬度分别是一组舞者和最大音乐会数量。
下面一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个舞者的尴尬程度。
输入中所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^6$$$。同样,输入中所有测试用例的 $$$m$$$ 值之和不超过 $$$10^6$$$。
输出
打印输入中所有测试用例的答案。
如果剧团根本无法举办音乐会,则只需打印一行“0”即可。在这种情况下,您不应打印任何其他内容。
如果剧团给出的音乐会数量为正数$$$r$$$($$$r$$$等于$$$m$$$的最小值和有效集的总数),则首先打印$$$r$$$的值,然后打印$$$r$$$行:第$$$j$$$行应包含两个整数$$$s_j$$$和$$$t_j$$$ — 第 $$$j$$$ 场音乐会中舞者的数量以及第 $$$j$$$ 场音乐会中舞者表演的总尴尬程度。使用描述最后一组的行完成测试用例的输出:准确打印 $$$s_r$$$ 从 $$$1$$$ 到 $$$n$$$ 的不同整数 — 将在第 $$$r$$$ 场(最后一场)音乐会上表演的舞者编号,按任意顺序。如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 7 13 10 3 1 5 1 8 2 13 2 10 1 12 12 3 32 100000 2 1 5
输出 #1
10 5 12 4 7 4 9 4 10 4 11 4 11 4 12 4 13 3 4 3 5 2 4 1 0 7 3 8 2 3 2 6 2 7 1 1 1 2 1 5 3