F. Поликарп и банкомат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп начал работать в банке. Ему назначили следить за банкоматом. В банкомате изначально есть $$$s$$$ рублей.

К нему выстроились очередь из $$$n$$$ студентов. Каждый студент хочет либо снять некоторое количество денег, либо внести на счёт. Если $$$a_i$$$ положительное, то студент зачисляет через банкомат такое количество денег. В противном случае — снимает $$$|a_i|$$$ рублей.

В начале в банкомате $$$s$$$ рублей и он отключён. Поликарп пропускает произвольное количество студентов. В какой-то момент времени Поликарп включает банкомат. Затем банкомат начинает обcлуживать оставшихся студентов по очереди. Если в какой-то момент времени в банкомате меньше рублей, чем хочет снять студент, тогда студент не обслуживается и Поликарп выключает банкомат и больше его никогда не включает.

Более формально, студенты, которые будут обслужены образуют непрерывную подпоследовательность.

Поликарп хочет, чтобы банкомат обслужил наибольшее количество студентов. Помогите ему в этом деле. Выведите номера первого и последнего студента или определите, что он не сможет никого обслужить.

Иными словами, найдите такой максимальный по длине непрерывный подотрезок студентов, что, начав с суммы $$$s$$$ в банкомате, все эти студенты будут обслужены. Банкомат обслуживает студентов последовательно в порядке очереди.

Входные данные

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Каждый набор входных данных состоит из двух строк. В первой из них записаны целые числа $$$n$$$ и $$$s$$$ ($$$1 \le n \le 2\cdot10^5$$$; $$$0 \le s \le 10^9$$$) — длина массива $$$a$$$ и начальное количество рублей в банкомате. Во второй записаны $$$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.

Если есть несколько возможных ответов, выведите любой.

Пример
Входные данные
3
4 10
-16 2 -6 8
3 1000
-100000 -100000 -100000
6 0
2 6 -164 1 -1 -6543
Выходные данные
2 4
-1
1 2
Примечание

В первом наборе входных данных единственным правильным ответом является 2 4, так как при обслуживании студентов количество рублей в банкомате не становится отрицательным, и это максимальное количество студентов, которое возможно обслужить.

Во втором наборе входных данных ответ -1, так как для любого студента в банкомате недостаточно денег.

В третьем наборе входных данных ответ может быть как 1 2, так и 4 5.