CF1250I Show Must Go On

著名舞蹈秀的导演计划进行一场巡演。已经决定，这次巡演最多包含 $m$ 场演出。 舞团中有 $n$ 名舞者。每位舞者都有一个尴尬值，第 $i$ 位舞者的尴尬值为 $a_i$。 导演喜欢多样性。因此，每场演出都由不同的舞者组合表演。每位舞者可以参加多场演出。例如，某一场演出由一组舞者表演，另一场演出可以由这组舞者的子集表演。唯一的限制是，同一组舞者不能重复表演。 导演更喜欢人数多的舞者组合。如果两组舞者人数相同，则导演更喜欢尴尬值总和较小的组合。如果两组舞者人数和尴尬值总和都相同，则导演对这两组没有偏好。 市场调研显示，如果一场演出中所有舞者的尴尬值总和超过 $k$，观众将不会前来观看。 导演希望为 $m$ 场演出制定最佳方案。他打算列出所有可能的舞者组合，然后剔除尴尬值总和超过 $k$ 的组合。剩下的舞者组合按照导演的偏好排序。最受偏好的组合将进行第一场演出，第二受偏好的组合进行第二场演出，依此类推，直到第 $m$ 场。如果有效组合总数少于 $m$，则实际演出场数等于有效组合数。 现在，导演把制定方案的任务交给了你！请注意，由于导演对人数和尴尬值总和都相同的组合没有偏好，因此可能存在多种可行方案。在这种情况下，任意一种方案都可以。对于每场演出，请输出舞者人数和尴尬值总和。对于最后一场演出，请输出其舞者的编号。

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据第一行包含三个整数 $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$ 场演出的舞者人数和尴尬值总和。最后，输出一行描述最后一场演出的组合：输出恰好 $s_r$ 个互不相同的整数，范围为 $1$ 到 $n$，表示参加第 $r$ 场（最后一场）演出的舞者编号，顺序任意。如果有多种答案，输出任意一种即可。

由 ChatGPT 4.1 翻译