CF1611F.ATM and Students

Polycarp started working at a bank. He was assigned to monitor the ATM. The ATM initially contains $s$ rubles.

A queue of $n$ students lined up to him. Each student wants to either withdraw a certain amount of money or deposit it into an account. If $a_i$ is positive, then the student credits that amount of money via ATM. Otherwise, the student withdraws $|a_i|$ rubles.

In the beginning, the ATM is turned off and an arbitrary number of students are not served. At some point, Polycarp turns on the ATM, which has an initial amount of $s$ rubles. Then, the remaining students start queueing at the ATM. If at some point in time there is less money in the ATM than the student wants to withdraw, then the student is not served and Polycarp turns off the ATM and does not turn it on anymore.

More formally, the students that are served are forming a contiguous subsequence.

Polycarp wants the ATM to serve the maximum number of students. Help him in this matter. Print the numbers of the first and last student, or determine that he will not be able to serve anyone.

In other words, find such a longest continuous segment of students that, starting with the sum of $s$ at the ATM, all these students will be served. ATM serves students consistently (i.e. one after another in the order of the queue).

波利卡普开始在一家银行工作，被指派监控一台自动取款机（ATM）。该 ATM 初始时含有 $s$ 卢布。

有 $n$ 名学生排成一队等待办理业务。每名学生希望从 ATM 取出一定金额的钱，或向账户存入一定金额的钱。若 $a_i$ 为正数，则该学生通过 ATM 存入该金额；否则，该学生从 ATM 取出 $|a_i|$ 卢布。

初始时，ATM 处于关闭状态，且任意数量的学生可能未被服务。在某一时刻，波利卡普开启 ATM，此时 ATM 中的金额为 $s$ 卢布。随后，剩余的学生开始依次在 ATM 前排队办理业务。若在某一时刻，ATM 中的余额少于某位学生欲取出的金额，则该学生无法被服务，波利卡普立即关闭 ATM，且此后不再开启。

更准确地说，被服务的学生构成一个连续的子序列。

波利卡普希望 ATM 能服务尽可能多的学生。请帮助他解决这一问题：输出首位与末位被服务学生的编号；若无法服务任何学生，则说明这一点。

换言之，请找出最长的连续学生段，使得以 ATM 初始金额 $s$ 开始，该段中所有学生均能被依次成功服务（即按队列顺序逐个处理）。

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

Each test case consists of two lines. The first one contains integers $n$ and $s$ ($1 \le n \le 2\cdot10^5$; $0 \le s \le 10^9$) — the length of the $a$ array and the initial amount of rubles in the ATM. The second contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) — elements of the $a$ array. Note that $a_i$ can be zero.

It is guaranteed that the sum of the values $n$ over all test cases does not exceed $2\cdot10^5$.

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

Print $t$ lines, each line must contain the answer to the corresponding set of input data: if the answer exists, print the numbers of the first and last served student. If there is no solution, then print -1 on the line.

If there are several possible answers, print any.

输出 $t$ 行，每行必须包含对应输入数据组的答案：如果答案存在，则输出最先和最后被服务的学生的编号；如果无解，则在该行输出 -1。

如果存在多个可能的答案，输出任意一个即可。

In the first test case, the only correct answer is 2 4, since when serving students, the number of rubles at the ATM does not become negative, and this is the maximum number of students that can be served.

In the second test case, the answer is -1, as there is not enough money for any student at the ATM.

In the third test case, the answer can be either 1 2 or 4 5.

在第一个测试用例中，唯一正确的答案是 2 4，因为服务学生时自动取款机（ATM）中的卢布数量不会变为负数，且这是能够服务的学生的最大数量。

在第二个测试用例中，答案为 -1，因为 ATM 中没有足够的钱来服务任何一名学生。

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