ATM and Students

题意翻译

Polycarp 开始在一家银行工作。他被派去管理一台自动取款机（ATM）。 ATM 里面最初有 $s$ 卢布。 一排 $n$ 个学生在他面前排队办理业务。每个学生都想提取出 $|a_i|$ 卢布或存入 $|a_i|$ 卢布。如果 $a_i$ 是正数，则学生通过 ATM 存入 $|a_i|$ 卢布；否则，学生取出 $|a_i|$ 卢布。 一开始，自动取款机关闭，不为前面的学生提供服务。在某个时候，Polycarp 打开 ATM，里面有 $s$ 卢布。然后，剩下的学生开始在自动取款机前排队。如果在某个时间点 ATM 中的钱少于学生想要取款的金额，则 ATM 不会继续为该学生以及后面的学生提供服务，Polycarp 会关闭 ATM 并且不再打开它。 形式化地说，被服务的学生是序列 $a$ 的一个连续的子串。 Polycarp 希望 ATM 能够为尽量多的学生提供服务。请你帮助他解决这个问题。输出在被服务的学生人数最多的情况下，第一个和最后一个被服务的学生的序号，或者判断是否无法给任何人服务（无解）。 更简单的题意： 给定一个长度为 $n$ 的序列 $a$ 和一个整数 $s$，求一段最长的区间 $[l,r]$ 使得 $\forall i\in[l,r],s+\sum\limits_{j=l}^i a_j\geq 0$。

题目描述

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).

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #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

说明

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.