← 返回题目列表

Codeforces · 1611/F

F. ATM 和学生

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

Polycarp 开始在一家银行工作。他被指派监视 ATM 机。 ATM 最初包含 $$$s$$$ 卢布。

一队 $$$n$$$ 学生在他面前排队。每个学生都想提取一定数量的钱或将其存入帐户。如果 $$$a_i$$$ 为正数,则学生通过 ATM 存入该金额。否则,学生提取 $$$|a_i|$$$ 卢布。

一开始,ATM 被关闭,并且不为任意数量的学生提供服务。在某个时刻,波利卡普打开了 ATM,初始金额为 $$$s$$$ 卢布。然后,剩下的学生开始在ATM机前排队。如果在某个时间点,ATM 中的钱少于学生想要提取的金额,则不会为学生提供服务,Polycarp 会关闭 ATM,不再打开它。

更正式地说,接受服务的学生正在形成一个连续的子序列。

Polycarp 希望 ATM 为最大数量的学生提供服务。在这件事上帮助他。打印第一个和最后一个学生的号码,或者确定他无法为任何人服务。

换句话说,找到最长的连续学生段,从 ATM 上的 $$$s$$$ 总和开始,所有这些学生都将得到服务。 ATM 始终如一地为学生提供服务(即按照队列顺序依次服务)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成。第一个包含整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n \le 2\cdot10^5$$$; $$$0 \le s \le 10^9$$$) — $$$a$$$ 数组的长度和 ATM 中卢布的初始数量。第二个包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — $$$a$$$ 数组的元素。请注意,$$$a_i$$$ 可以为零。

保证所有测试用例的值 $$$n$$$ 之和不超过 $$$2\cdot10^5$$$。

输出

打印 $$$t$$$ 行,每行必须包含相应输入数据集的答案:如果答案存在,则打印第一个和最后一个服务的学生的号码。如果无解,则在该行打印-1。

如果有多个可能的答案,请打印任何一个。

示例

输入 #1

3
4 10
-16 2 -6 8
3 1000
-100000 -100000 -100000
6 0
2 6 -164 1 -1 -6543

输出 #1

2 4
-1
1 2

注意

在第一个测试用例中,唯一正确的答案是 2 4,因为在为学生提供服务时,ATM 上的卢布数量不会变成负数,这是可以服务的最大学生数量。

在第二个测试用例中,答案为 -1,因为 ATM 上没有足够的钱供任何学生使用。

在第三个测试用例中,答案可以是 1 2 或 4 5。