CF1070E.Getting Deals Done

Polycarp has a lot of work to do. Recently he has learned a new time management rule: "if a task takes five minutes or less, do it immediately". Polycarp likes the new rule, however he is not sure that five minutes is the optimal value. He supposes that this value $d$ should be chosen based on existing task list.

Polycarp has a list of $n$ tasks to complete. The $i$-th task has difficulty $p_i$, i.e. it requires exactly $p_i$ minutes to be done. Polycarp reads the tasks one by one from the first to the $n$-th. If a task difficulty is $d$ or less, Polycarp starts the work on the task immediately. If a task difficulty is strictly greater than $d$, he will not do the task at all. It is not allowed to rearrange tasks in the list. Polycarp doesn't spend any time for reading a task or skipping it.

Polycarp has $t$ minutes in total to complete maximum number of tasks. But he does not want to work all the time. He decides to make a break after each group of $m$ consecutive tasks he was working on. The break should take the same amount of time as it was spent in total on completion of these $m$ tasks.

For example, if $n=7$, $p=[3, 1, 4, 1, 5, 9, 2]$, $d=3$ and $m=2$ Polycarp works by the following schedule:

• Polycarp reads the first task, its difficulty is not greater than $d$ ($p_1=3 \le d=3$) and works for $3$ minutes (i.e. the minutes $1$, $2$, $3$);
• Polycarp reads the second task, its difficulty is not greater than $d$ ($p_2=1 \le d=3$) and works for $1$ minute (i.e. the minute $4$);
• Polycarp notices that he has finished $m=2$ tasks and takes a break for $3+1=4$ minutes (i.e. on the minutes $5, 6, 7, 8$);
• Polycarp reads the third task, its difficulty is greater than $d$ ($p_3=4 \gt d=3$) and skips it without spending any time;
• Polycarp reads the fourth task, its difficulty is not greater than $d$ ($p_4=1 \le d=3$) and works for $1$ minute (i.e. the minute $9$);
• Polycarp reads the tasks $5$ and $6$, skips both of them ($p_5 \gt d$ and $p_6 \gt d$);
• Polycarp reads the $7$-th task, its difficulty is not greater than $d$ ($p_7=2 \le d=3$) and works for $2$ minutes (i.e. the minutes $10$, $11$);
• Polycarp notices that he has finished $m=2$ tasks and takes a break for $1+2=3$ minutes (i.e. on the minutes $12, 13, 14$).

Polycarp stops exactly after $t$ minutes. If Polycarp started a task but has not finished it by that time, the task is not considered as completed. It is allowed to complete less than $m$ tasks in the last group. Also Polycarp considers acceptable to have shorter break than needed after the last group of tasks or even not to have this break at all — his working day is over and he will have enough time to rest anyway.

Please help Polycarp to find such value $d$, which would allow him to complete maximum possible number of tasks in $t$ minutes.

波利卡普有很多工作要做。最近，他学习了一种新的时间管理规则：“如果一项任务耗时不超过五分钟，就立即完成它”。波利卡普很喜欢这条新规则，但他不确定五分钟是否是最优值。他认为该阈值 $d$ 应当根据当前的任务列表来确定。

波利卡普有一份包含 $n$ 项任务的待办清单。第 $i$ 项任务的难度为 $p_i$，即恰好需要 $p_i$ 分钟才能完成。波利卡普按顺序从第 $1$ 项到第 $n$ 项逐一阅读任务。若某项任务的难度不超过 $d$（即 $p_i \le d$），则波利卡普立即开始执行该任务；若某项任务的难度严格大于 $d$（即 $p_i > d$），则他完全跳过该任务。不允许重新排列任务顺序。波利卡普在阅读或跳过任务时不消耗任何时间。

波利卡普总共拥有 $t$ 分钟的时间，目标是在该时间内完成尽可能多的任务。但他并不想连续工作整段时间。他决定：每完成连续 $m$ 项任务后，就休息一次；休息时长应等于这 $m$ 项任务所耗费的总时间。

例如，当 $n=7$，$p=[3, 1, 4, 1, 5, 9, 2]$，$d=3$ 且 $m=2$ 时，波利卡普的工作安排如下：

• 波利卡普阅读第一项任务，其难度未超过 $d$（$p_1 = 3 \le d = 3$），立即执行，耗时 $3$ 分钟（即第 $1, 2, 3$ 分钟）；
• 波利卡普阅读第二项任务，其难度未超过 $d$（$p_2 = 1 \le d = 3$），立即执行，耗时 $1$ 分钟（即第 $4$ 分钟）；
• 波利卡普注意到已连续完成 $m = 2$ 项任务，于是休息 $3 + 1 = 4$ 分钟（即第 $5, 6, 7, 8$ 分钟）；
• 波利卡普阅读第三项任务，其难度大于 $d$（$p_3 = 4 > d = 3$），直接跳过，不消耗时间；
• 波利卡普阅读第四项任务，其难度未超过 $d$（$p_4 = 1 \le d = 3$），立即执行，耗时 $1$ 分钟（即第 $9$ 分钟）；
• 波利卡普阅读第 $5$ 和第 $6$ 项任务，均因 $p_5 > d$、$p_6 > d$ 而跳过；
• 波利卡普阅读第 $7$ 项任务，其难度未超过 $d$（$p_7 = 2 \le d = 3$），立即执行，耗时 $2$ 分钟（即第 $10, 11$ 分钟）；
• 波利卡普注意到已连续完成 $m = 2$ 项任务，于是休息 $1 + 2 = 3$ 分钟（即第 $12, 13, 14$ 分钟）。

波利卡普恰好在 $t$ 分钟后停止。若他在 $t$ 分钟内启动了某项任务但尚未完成，则该任务不计为完成。最后一组任务允许少于 $m$ 项；此外，在最后一组任务完成后，其对应的休息时间可以短于规定时长，甚至可以完全省略——因为他的工作日已经结束，之后自然有充足时间休息。

请帮助波利卡普找出一个阈值 $d$，使得他在 $t$ 分钟内能够完成尽可能多的任务。

The first line of the input contains single integer $c$ ($1 \le c \le 5 \cdot 10^4$) — number of test cases. Then description of $c$ test cases follows. Solve test cases separately, test cases are completely independent and do not affect each other.

Each test case is described by two lines. The first of these lines contains three space-separated integers $n$, $m$ and $t$ ($1 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5, 1 \le t \le 4 \cdot 10^{10}$) — the number of tasks in Polycarp's list, the number of tasks he can do without a break and the total amount of time Polycarp can work on tasks. The second line of the test case contains $n$ space separated integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 2 \cdot 10^5$) — difficulties of the tasks.

The sum of values $n$ for all test cases in the input does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $c$（$1 \le c \le 5 \cdot 10^4$），表示测试用例的数量。随后是 $c$ 个测试用例的描述。请独立求解每个测试用例，各测试用例之间完全独立，互不影响。

每个测试用例由两行描述。第一行包含三个以空格分隔的整数 $n$、$m$ 和 $t$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$，$1 \le t \le 4 \cdot 10^{10}$），分别表示 Polycarp 待办任务列表中的任务数量、他连续可完成的任务数量（无需休息），以及 Polycarp 可用于处理任务的总时间。测试用例的第二行包含 $n$ 个以空格分隔的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le 2 \cdot 10^5$），表示各任务的难度。

输入中所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

Print $c$ lines, each line should contain answer for the corresponding test case — the maximum possible number of tasks Polycarp can complete and the integer value $d$ ($1 \le d \le t$) Polycarp should use in time management rule, separated by space. If there are several possible values $d$ for a test case, output any of them.

输出 $c$ 行，每行应包含对应测试用例的答案：Polycarp 最多能完成的任务数，以及时间管理规则中应使用的整数 $d$（$1 \le d \le t$），二者以空格分隔。若某个测试用例存在多个可能的 $d$ 值，则输出其中任意一个即可。

In the first test case of the first example $n=5$, $m=2$ and $t=16$. The sequence of difficulties is $[5, 6, 1, 4, 7]$. If Polycarp chooses $d=5$ then he will complete $3$ tasks. Polycarp will work by the following schedule:

• Polycarp reads the first task, its difficulty is not greater than $d$ ($p_1=5 \le d=5$) and works for $5$ minutes (i.e. the minutes $1, 2, \dots, 5$);
• Polycarp reads the second task, its difficulty is greater than $d$ ($p_2=6 \gt d=5$) and skips it without spending any time;
• Polycarp reads the third task, its difficulty is not greater than $d$ ($p_3=1 \le d=5$) and works for $1$ minute (i.e. the minute $6$);
• Polycarp notices that he has finished $m=2$ tasks and takes a break for $5+1=6$ minutes (i.e. on the minutes $7, 8, \dots, 12$);
• Polycarp reads the fourth task, its difficulty is not greater than $d$ ($p_4=4 \le d=5$) and works for $4$ minutes (i.e. the minutes $13, 14, 15, 16$);
• Polycarp stops work because of $t=16$.

In total in the first test case Polycarp will complete $3$ tasks for $d=5$. He can't choose other value for $d$ to increase the number of completed tasks.

在第一个示例的第一个测试用例中，$n=5$，$m=2$，$t=16$。难度序列为 $[5, 6, 1, 4, 7]$。若 Polycarp 选择 $d=5$，则他将完成 $3$ 个任务。Polycarp 的工作安排如下：

• Polycarp 阅读第一个任务，其难度不大于 $d$（即 $p_1=5 \le d=5$），并花费 $5$ 分钟完成（即第 $1, 2, \dots, 5$ 分钟）；
• Polycarp 阅读第二个任务，其难度大于 $d$（即 $p_2=6 \gt d=5$），因此跳过该任务，不消耗任何时间；
• Polycarp 阅读第三个任务，其难度不大于 $d$（即 $p_3=1 \le d=5$），并花费 $1$ 分钟完成（即第 $6$ 分钟）；
• Polycarp 注意到自己已完成了 $m=2$ 个任务，于是休息 $5+1=6$ 分钟（即第 $7, 8, \dots, 12$ 分钟）；
• Polycarp 阅读第四个任务，其难度不大于 $d$（即 $p_4=4 \le d=5$），并花费 $4$ 分钟完成（即第 $13, 14, 15, 16$ 分钟）；
• Polycarp 因达到时限 $t=16$ 而停止工作。

综上，在第一个测试用例中，当 $d=5$ 时，Polycarp 总共完成 $3$ 个任务。他无法选择其他 $d$ 值来增加完成的任务数量。