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


-----Input-----

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


-----Output-----

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.


-----Examples-----

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


-----Note-----

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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis


Solutions:
def solve(studentActivity, n, s):
	maxContiguousLength = 0
	firstIndex = -1
	rangeList = [-1]
	curActivitySum = s
	for (lastIndex, activity) in enumerate(studentActivity):
		curActivitySum += activity
		while curActivitySum < 0 and firstIndex < lastIndex:
			firstIndex += 1
			curActivitySum -= studentActivity[firstIndex]
		curActivityLength = lastIndex - firstIndex
		if curActivityLength > maxContiguousLength:
			rangeList = [firstIndex + 2, lastIndex + 1]
			maxContiguousLength = curActivityLength
	print(*rangeList)
for case in range(int(input())):
	(n, s) = map(int, input().split())
	studentActivity = list(map(int, input().split()))
	solve(studentActivity, n, s)


def f():
	(n, t) = map(int, input().split())
	l = list(map(int, input().split()))
	d = 0
	(x, y) = (0, 0)
	(p, q) = (-1, -1)
	for i in range(n):
		if t + l[i] >= 0:
			y += 1
			t += l[i]
		else:
			if d < y - x:
				d = y - x
				(p, q) = (x, y)
			while t + l[i] < 0 and x != y:
				t -= l[x]
				x += 1
			y += 1
			if t + l[i] < 0:
				x += 1
			else:
				t += l[i]
		if d < y - x:
			d = y - x
			(p, q) = (x, y)
	if d:
		return [p + 1, q]
	else:
		return [-1]
for _ in range(int(input())):
	print(*f())


for _ in range(int(input())):
	(n, s) = map(int, input().split())
	arr = [-1] + list(map(int, input().split()))
	maxSoFar = x = y = 0
	left = 1
	curr = s
	for right in range(1, n + 1):
		curr += arr[right]
		while curr < 0:
			curr -= arr[left]
			left += 1
		if right - left + 1 > maxSoFar:
			maxSoFar = right - left + 1
			x = left
			y = right
	print(f'{x} {y}' if maxSoFar else -1)


def main():
	t = int(input())
	for i in range(t):
		(n, s) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		(l1, l2, r_l1, r_l2) = (0, 0, 0, 0)
		summa = 0
		while l1 < n:
			if l2 < l1:
				l2 = l1
				summa = 0
			while l2 < n and summa + a[l2] + s >= 0:
				summa += a[l2]
				l2 += 1
			if r_l2 - r_l1 < l2 - l1:
				(r_l2, r_l1) = (l2, l1)
			summa -= a[l1]
			l1 += 1
		print(r_l1 + 1, r_l2) if r_l1 < r_l2 else print(-1)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = [-1 * i for i in arr]
	subarray_start = 0
	subarray_end = 0
	st = -1
	e = -1
	subarray_sum = 0
	max_len = -1
	for i in s:
		subarray_sum += i
		subarray_end += 1
		while subarray_sum > k:
			subarray_sum -= s[subarray_start]
			subarray_start += 1
		if subarray_end - subarray_start > max_len:
			max_len = subarray_end - subarray_start
			st = subarray_start
			e = subarray_end
	if st == 1 and e == 1:
		print(-1)
	else:
		print(st + 1, e)


cases = int(input())
for _ in range(cases):
	(n, s) = map(int, input().split())
	lst = list(map(int, input().split()))
	left = 0
	end = -1
	available = s
	students = 0
	for (right, n) in enumerate(lst):
		available += n
		while available < 0:
			available -= lst[left]
			left += 1
		student_window = right - left + 1
		if student_window > students:
			students = student_window
			end = right
	if end == -1:
		print(-1)
	else:
		end += 1
		print(end - students + 1, end)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	(n, s) = M()
	a = L()
	i = j = 0
	c = s
	m = -1
	p = q = -1
	for k in a:
		c += k
		j += 1
		if c >= 0:
			if m < j - i:
				m = j - i
				(p, q) = (i + 1, j)
		else:
			while c < 0:
				c -= a[i]
				i += 1
	if m == -1:
		print(-1)
	else:
		print(p, q)


for _ in range(int(input())):
	(n, s) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = 0
	ans = -1
	temp = 0
	res = []
	for (r, el) in enumerate(arr):
		temp += el
		while l <= r and temp + s < 0:
			temp -= arr[l]
			l += 1
		if l > r:
			pass
		elif ans < r - l + 1:
			ans = r - l + 1
			res = [l, r]
	if ans == -1:
		print(ans)
	else:
		print(res[0] + 1, res[1] + 1)


import sys
input = sys.stdin.readline
nn = int(input())
for _ in range(nn):
	(n, s) = map(int, input().split())
	nums = list(map(int, input().split()))
	(l, r, total, length) = (0, 0, 0, [0, 0, 0])
	for r in range(n):
		total += nums[r]
		while l <= r and total < -s:
			total -= nums[l]
			l += 1
		if r - l + 1 > length[0]:
			length = [r - l + 1, l + 1, r + 1]
	print(*length[1:]) if length[0] > 0 else print(-1)


t = int(input())
answers = []
for _ in range(t):
	(n, s) = map(int, input().split())
	a = [int(x) for x in input().split()]
	(l, r, lmax, rmax, cur_max) = (0, 0, 0, -1, 0)
	for i in range(n):
		s += a[i]
		cur_max += 1
		while s < 0:
			s -= a[l]
			l += 1
			cur_max -= 1
		if rmax - lmax + 1 < cur_max:
			lmax = l
			rmax = r
		r += 1
	if rmax == -1:
		print(-1)
	else:
		print(str(lmax + 1) + ' ' + str(rmax + 1))


t = int(input())
for i in range(t):
	(n, s) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	if n == 1:
		if s + a[0] >= 0:
			print(1, 1)
		else:
			print(-1)
	else:
		curfp = 0
		curlp = 0
		curlength = 0
		maxfp = 0
		maxlp = 0
		maxlength = 0
		temp_sum = a[0]
		while curlp != n - 1:
			if temp_sum + s >= 0:
				temp_sum += a[curlp + 1]
				curlength += 1
				curlp += 1
			elif curfp == curlp:
				temp_sum = a[curlp + 1]
				curfp += 1
				curlp += 1
			else:
				if curlength > maxlength:
					maxlength = curlength
					maxfp = curfp
					maxlp = curlp - 1
				temp_sum -= a[curfp]
				curfp += 1
				curlength -= 1
		if curlp - curfp + 1 > maxlength and temp_sum + s >= 0:
			maxlength = curlp - curfp + 1
			maxfp = curfp
			maxlp = curlp
		elif curlength > maxlength:
			maxlength = curlength
			maxfp = curfp
			maxlp = curlp - 1
		if maxlength > 0:
			print(maxfp + 1, maxlp + 1)
		else:
			print(-1)


t = int(input())
for _ in range(t):
	(n, s) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = [-1]
	(mxlen, i, j, cs, w) = [0] * 5
	while 1:
		if cs >= -s:
			if j - i > mxlen:
				mxlen = j - i
				ans = [i + 1, j]
			if j >= n:
				break
			cs += a[j]
			j += 1
			continue
		cs = cs - a[i]
		i += 1
	print(*ans)


f = lambda : [*map(int, input().split())]
for _ in [0] * f()[0]:
	(n, s) = f()
	(a, x) = (f(), [-1])
	(l, b, e, t, w) = [0] * 5
	while 1:
		if w >= -s:
			if e - b > l:
				l = e - b
				x = [b + 1, e]
			if e >= n:
				print(*x)
				break
			t += a[e]
			w = min(w, t)
			e += 1
		else:
			w = t = t - a[b]
			b += 1


import sys
printer = []
for _ in range(int(sys.stdin.readline())):
	(n, s) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	(i, j) = (0, 0)
	atm = s
	ans = -1
	(L, R) = (0, 0)
	while j < n:
		if a[j] + atm >= 0:
			atm += a[j]
			j += 1
		else:
			atm -= a[i]
			i += 1
		if ans < j - i:
			ans = j - i
			(L, R) = (i + 1, j)
	if L > R:
		printer.append('-1')
	else:
		printer.append(str(L) + ' ' + str(R))
print('\n'.join(printer))


import sys
sys.stdin.readline
tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ans = 0
	l = 0
	r = 0
	sum = k
	maxd = 0
	resL = -1
	resr = -1
	while r <= len(ar) - 1:
		sum += ar[r]
		if sum < 0:
			r += 1
			while l < r and sum < 0:
				sum -= ar[l]
				l += 1
		else:
			dist = r - l + 1
			if maxd < dist:
				resL = l + 1
				resr = r + 1
				maxd = max(maxd, dist)
			r += 1
	if resL == -1:
		print(-1)
	else:
		print(resL, resr)


test = int(input())
for _ in range(test):
	(n, s) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	(left, right) = (0, 0)
	ans = [0, -1, -1]
	while right < n:
		if arr[right] >= 0:
			s += arr[right]
			right += 1
		elif s + arr[right] >= 0:
			s += arr[right]
			right += 1
		else:
			if right - left > ans[0]:
				ans[0] = right - left
				ans[1] = left
				ans[2] = right - 1
			if left < right:
				s -= arr[left]
				left += 1
			else:
				left += 1
				right += 1
	while left < right:
		if right - left > ans[0]:
			ans[0] = right - left
			ans[1] = left
			ans[2] = right - 1
		if left < right:
			s -= arr[left]
			left += 1
		else:
			left += 1
			right += 1
	if ans[0]:
		print(ans[1] + 1, ans[2] + 1)
	else:
		print(-1)


import itertools, operator
T = int(input())
for t in range(T):
	(n, s) = map(int, input().split())
	a = list(itertools.accumulate(map(lambda x: -int(x), input().split()), func=operator.add, initial=0))
	(x, y, l) = (-1, -1, 0)
	(i, j) = (1, 1)
	while j < n + 1:
		if a[j] - a[i - 1] <= s:
			j += 1
			if l < j - i:
				(x, y, l) = (i, j, j - i)
		else:
			i += 1
		if i > j:
			j = i
	if i <= n:
		if l < j - i + 1:
			(x, y, l) = (i, j, j - i + 1)
	if l:
		print(x, y - 1)
	else:
		print(-1)


tc = int(input())
for case in range(tc):
	(n, suma) = (int(i) for i in input().split())
	queries = [int(j) for j in input().split()]
	indice = -1
	final = -1
	maximo = 0
	for pos in range(n):
		valor = queries[pos]
		if suma + valor >= 0:
			if indice == -1:
				indice = pos
				final = pos
				suma += valor
			else:
				suma += valor
				final = pos
			longitud = final - indice + 1
			if longitud > maximo:
				last_indice = indice
				last_final = final
			maximo = max(maximo, longitud)
		elif indice != -1:
			suma += queries[pos]
			for j in range(indice, pos + 1):
				suma -= queries[j]
				if suma >= 0:
					indice = j + 1
					break
	if indice == -1:
		print(-1)
	else:
		print(last_indice + 1, last_final + 1)


T = int(input())
for _ in range(T):
	(n, s) = map(int, input().split())
	a = list(map(int, input().split()))
	(l, r, m) = (0, 0, 0)
	add = 0
	interm = 0
	while r < n:
		if s + add >= 0 and s + add + a[r] >= 0:
			add += a[r]
			if m < r - l + 1:
				ans = [l, r]
				m = r - l + 1
			r += 1
		elif l == r:
			add = 0
			l += 1
			r += 1
		else:
			add -= a[l]
			l += 1
	if m == 0:
		print('-1')
	else:
		print(f'{ans[0] + 1} {ans[1] + 1}')


from collections import deque
from math import inf

def solve(s, a):
	prefix = [0] * len(a)
	prefix[0] = a[0]
	for k in range(1, len(a)):
		prefix[k] = prefix[k - 1] + a[k]

	def subsum(x, y):
		if x == 0:
			return prefix[y]
		return prefix[y] - prefix[x - 1]
	d = deque()
	max_students_served = -inf
	best_pair = (-1, -1)
	for last_served in range(len(a)):
		d.append(last_served)
		while d and subsum(d[0], last_served) + s < 0:
			d.popleft()
		if d and last_served - d[0] + 1 > max_students_served:
			max_students_served = last_served - d[0] + 1
			best_pair = (d[0], last_served)
	return best_pair
t = int(input())
for _ in range(t):
	(n, s) = [int(q) for q in input().split(' ')]
	a = [int(q) for q in input().split(' ')]
	(p, q) = solve(s, a)
	if (p, q) == (-1, -1):
		print('-1')
	else:
		print(p + 1, q + 1)


t = int(input())
for _ in range(t):
	(n, s) = map(int, input().split())
	a = list(map(int, input().split()))
	(left, right) = (0, 0)
	for i in range(1, n):
		a[i] += a[i - 1]
	a = [0] + a
	(i, j) = (0, 0)
	while j <= n:
		if a[j] - a[i] + s >= 0:
			if j - i > right - left:
				(left, right) = (i, j)
			j += 1
		else:
			i += 1
	if left == right:
		print(-1)
	else:
		print(left + 1, right)


from sys import stdin

def sng_int():
	return int(stdin.readline())

def sng_str():
	return stdin.readline()

def int_list():
	return list(map(int, stdin.readline().split()))
t = sng_int()
for _ in range(t):
	(n, s) = map(int, sng_str().split())
	arr = int_list()
	i = 0
	j = 0
	(l, r) = (0, -1)
	while j < n:
		while j < n and s + arr[j] >= 0:
			s += arr[j]
			j += 1
		if j - i > r - l:
			l = i
			r = j
		if j < n:
			while i <= j and s + arr[j] < 0:
				s -= arr[i]
				i += 1
	if l + 1 <= r:
		print(l + 1, r)
	else:
		print('-1')


n = int(input().split()[0])
for i in range(n):
	(l, s) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = ''
	_maxlen = -1
	i = 0
	j = i
	curr = s
	while i < len(arr) and j < len(arr):
		if arr[j] >= 0:
			curr += arr[j]
			j += 1
		elif arr[j] < 0:
			if curr >= abs(arr[j]):
				curr -= abs(arr[j])
				j += 1
			elif curr < abs(arr[j]):
				a = i + 1
				b = j
				if b - a > _maxlen:
					ans = str(a) + ' ' + str(b)
					_maxlen = b - a
				curr -= arr[i]
				i += 1
	a = i + 1
	b = j
	if b - a > _maxlen:
		ans = str(a) + ' ' + str(b)
		_maxlen = b - a
	if len(ans) > 0:
		print(ans)
	else:
		print(-1)