CF1250I.Show Must Go On

The director of the famous dance show plans a tour. It is already decided that the tour will consist of up to $m$ concerts.

There are $n$ dancers in the troupe. Each dancer is characterized by her awkwardness: the awkwardness of the $i$-th dancer is equal to $a_i$.

The director likes diversity. For this reason, each concert will be performed by a different set of dancers. A dancer may perform in multiple concerts. For example, it is possible that a set of dancers performs in one concert and a subset of this set of dancers performs in another concert. The only constraint is that the same set of dancers cannot perform twice.

The director prefers the set with larger number of dancers over the set with smaller number of dancers. If two sets consist of the same number of dancers, then the director prefers the one which has smaller sum of awkwardness of dancers. If two sets of dancers are equal in size and total awkwardness, then the director does not have a preference which one is better.

A marketing study shows that viewers are not ready to come to a concert if the total awkwardness of all the dancers performing in the concert is greater than $k$.

The director wants to find the best plan for $m$ concerts. He thinks to write down all possible sets of dancers; then get rid of the sets with total awkwardness greater than $k$. The remaining sets of dancers will be sorted according to his preference. The most preferred set of dancers will give the first concert, the second preferred set — the second concert and so on until the $m$-th concert. If it turns out that the total number of valid sets is less than $m$, then the total number of concerts will be equal to the number of valid sets.

It turns out that the director delegated finding the plan to you! Please, notice that there might be several acceptable plans due to the fact that the director does not have a preference over sets of dancers with the same size and total awkwardness. In this case any of these plans is good enough. For each concert find the number of dancers and the total awkwardness of the set performing. Also, for the last concert find its set of dancers.

著名舞蹈秀的导演计划开展一场巡演。已确定此次巡演最多包含 $m$ 场演出。

舞团共有 $n$ 名舞者。每名舞者均具有一个“笨拙值”：第 $i$ 名舞者的笨拙值为 $a_i$。

导演崇尚多样性。因此，每场演出均由一组互不相同的舞者完成。一名舞者可参与多场演出。例如，某组舞者可在一场演出中登台，而该组的一个子集则可在另一场演出中登台。唯一的约束是：同一组舞者不能重复出演两场演出。

导演优先选择人数更多的舞者组合；若两组舞者人数相同，则他偏好总笨拙值更小的组合；若两组舞者人数相同且总笨拙值也相同，则导演对这两组无偏好（即认为二者等价）。

一项市场调研表明：若一场演出中所有参演舞者的总笨拙值超过 $k$，观众将不愿前往观看。

导演希望为 $m$ 场演出制定最优方案。他的设想是：首先列出所有可能的舞者组合；然后剔除其中总笨拙值大于 $k$ 的组合；再将剩余组合按其偏好规则排序——最偏好的组合用于第一场演出，次偏好的组合用于第二场演出，依此类推，直至第 $m$ 场演出。若有效组合总数少于 $m$，则实际演出场数即为有效组合的总数。

结果发现，导演已将制定该方案的任务交予你！请注意：由于导演对人数相同且总笨拙值也相同的舞者组合并无偏好，因此可能存在多个可行方案。此时，任一可行方案均可接受。请对每场演出，输出该场演出所用舞者组合的人数及总笨拙值；并对最后一场演出，额外输出其所用的具体舞者组合（即该组合中包含哪些舞者）。

The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases in the input. Then the test cases follow.

Each test case begins with a line containing three integers $n$, $k$ and $m$ ($1 \le n \le 10^6$, $1 \le k \le 10^{18}$, $1 \le m \le 10^6$) — the total number of dancers, the maximum acceptable awkwardness of a set of dancers and the maximum number of concerts, respectively.

The following line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$), where $a_i$ is the awkwardness of the $i$-th dancer.

The sum of the values of $n$ over all test cases in the input does not exceed $10^6$. Similarly, the sum of the values of $m$ over all test cases in the input does not exceed $10^6$.

第一行包含一个整数 $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$。

Print the answers to all test cases in the input.

If the troupe cannot give concerts at all, then simply print one line "0". In this case, you should not print anything else.

If the troupe gives a positive number of concerts $r$ ($r$ is equal to the minimum of $m$ and the total number of valid sets), then first print the value of $r$, then $r$ lines: the $j$-th line should contain two integers $s_j$ and $t_j$ — the number of dancers in the $j$-th concert and the total awkwardness of the dancers performing in the $j$-th concert. Complete the output to a test case with a line that describes the last set: print exactly $s_r$ distinct integers from $1$ to $n$ — the numbers of the dancers who will perform at the $r$-th (last) concert, in any order. If there are several answers, print any of them.

输出输入中所有测试用例的答案。

如果该演出团根本无法举办任何音乐会，则只需输出一行“0”。此时，你不应输出任何其他内容。

如果该演出团能够举办正整数场音乐会 $r$（其中 $r$ 等于 $m$ 与所有有效集合总数的较小值），则首先输出 $r$ 的值，随后输出 $r$ 行：第 $j$ 行应包含两个整数 $s_j$ 和 $t_j$ —— 分别表示第 $j$ 场音乐会的舞者人数，以及在第 $j$ 场音乐会中表演的所有舞者的总别扭度。接着，用一行描述最后一组（即第 $r$ 组）来完成该测试用例的输出：输出恰好 $s_r$ 个互不相同的、取自 $1$ 到 $n$ 的整数 —— 这些整数表示将在第 $r$ 场（即最后一场）音乐会中表演的舞者的编号，顺序任意。若存在多种可行答案，输出任意一种即可。