← 返回题目列表

Codeforces · 1250/I

I. 演出必须继续

中文机器翻译题面 查看原题

著名舞蹈表演的导演计划巡演。已经决定巡演将包括高达 $$$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