波利卡普还有很多工作要做。最近,他学到了一条新的时间管理规则:“如果一项任务需要五分钟或更短时间,请立即执行”。波利卡普喜欢这个新规则,但他不确定五分钟是最佳值。他认为这个值 $$$d$$$ 应该根据现有的任务列表来选择。
Polycarp 有一个需要完成的 $$$n$$$ 任务列表。第 $$$i$$$ 任务的难度为 $$$p_i$$$,即它需要 $$$p_i$$$ 分钟才能完成。 Polycarp 从第一个任务到第 $$$n$$$ 个任务逐个读取。如果任务难度为 $$$d$$$ 或更低,Polycarp 会立即开始执行该任务。如果任务难度严格大于$$$d$$$,他根本不会执行该任务。不允许重新排列列表中的任务。波利卡普不会花任何时间来阅读或跳过任务。
Polycarp 总共需要 $$$t$$$ 分钟才能完成最大数量的任务。但他不想一直工作。他决定在完成每组 $$$m$$$ 连续任务后休息一下。休息时间应该与完成这些 $$$m$$$ 任务所花费的总时间相同。
例如,如果 $$$n=7$$$、$$$p=[3, 1, 4, 1, 5, 9, 2]$$$、$$$d=3$$$ 和 $$$m=2$$$ Polycarp 按以下时间表工作:
- Polycarp 读取第一个任务,其难度不大于 $$$d$$$ ($$$p_1=3 \le d=3$$$) 并且工作 $$$3$$$ 分钟(即 $$$1$$$、$$$2$$$、$$$3$$$ 分钟);
- Polycarp 读取第二个任务,其难度不大于 $$$d$$$ ($$$p_2=1 \le d=3$$$) 并且工作 $$$1$$$ 分钟(即 $$$4$$$ 分钟);
- Polycarp 注意到他已经完成了 $$$m=2$$$ 任务并休息了 $$$3+1=4$$$ 分钟(即在 $$$5, 6, 7, 8$$$ 分钟);
- Polycarp 读到第三个任务,其难度大于 $$$d$$$ ($$$p_3=4 > d=3$$$) 并跳过它,不花任何时间;
- Polycarp 读取第四个任务,其难度不大于 $$$d$$$ ($$$p_4=1 \le d=3$$$) 并且工作 $$$1$$$ 分钟(即 $$$9$$$ 分钟);
- Polycarp 读取任务 $$$5$$$ 和 $$$6$$$,跳过它们($$$p_5>d$$$ 和 $$$p_6>d$$$);
- Polycarp 读取第 $$$7$$$ 个任务,其难度不大于 $$$d$$$ ($$$p_7=2 \le d=3$$$) 并工作 $$$2$$$ 分钟(即 $$$10$$$、$$$11$$$ 分钟);
- Polycarp 注意到他已经完成了 $$$m=2$$$ 任务并休息了 $$$1+2=3$$$ 分钟(即在 $$$12, 13, 14$$$ 分钟)。
Polycarp 在 $$$t$$$ 分钟后停止。如果波旅甲开始了一项任务但当时尚未完成,则该任务不被视为已完成。最后一组允许完成少于 $$$m$$$ 的任务。此外,Polycarp 认为在最后一组任务之后休息时间比需要的时间短,甚至根本不休息都是可以接受的——他的工作日结束了,无论如何他都有足够的时间休息。
请帮助 Polycarp 找到这样的值 $$$d$$$,这将使他能够在 $$$t$$$ 分钟内完成最大可能数量的任务。
输入
输入的第一行包含单个整数 $$$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 列表中的任务数量,数量他可以不间断地完成的任务数量以及波利卡普可以完成任务的总时间。测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 2 \cdot 10^5$$$) - 任务的难度。
输入中所有测试用例的值 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
打印 $$$c$$$ 行,每行应包含相应测试用例的答案 - Polycarp 可以完成的最大可能任务数以及整数值 $$$d$$$ ($$$1 \le d \le t$$$) Polycarp 应在时间管理规则中使用,以空格分隔。如果测试用例有多个可能的值$$$d$$$,则输出其中任何一个。
示例
输入 #1
4 5 2 16 5 6 1 4 7 5 3 30 5 6 1 4 7 6 4 15 12 5 15 7 20 17 1 1 50 100
输出 #1
3 5 4 7 2 10 0 25
输入 #2
3 11 1 29 6 4 3 7 5 3 4 7 3 5 3 7 1 5 1 1 1 1 1 1 1 5 2 18 2 3 3 7 5
输出 #2
4 3 3 1 4 5
注意
在第一个示例的第一个测试用例中 $$$n=5$$$、$$$m=2$$$ 和 $$$t=16$$$。难度顺序为$$$[5,6,1,4,7]$$$。如果Polycarp选择$$$d=5$$$那么他将完成$$$3$$$任务。波利卡普将按以下时间表工作:
- Polycarp 读取第一个任务,其难度不大于 $$$d$$$ ($$$p_1=5 \le d=5$$$) 并持续 $$$5$$$ 分钟(即 $$$1, 2, \dots, 5$$$ 分钟);
- Polycarp 读到第二个任务,其难度大于 $$$d$$$ ($$$p_2=6 > 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$$$而停止工作。
在第一个测试用例中,Polycarp 总共将完成 $$$3$$$ 任务,$$$d=5$$$。他无法为 $$$d$$$ 选择其他值来增加已完成任务的数量。