1699. K-квест

В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены `N` персонажей, с каждым из которых может встретиться игрок. От общения с `i`-м персонажем карма игрока меняется на величину `a_i`, которая может быть как положительной, так отрицательной или даже нулем.

Изначально карма игрока равна нулю. Для того чтобы пройти на следующий уровень, нужно чтобы карма была в точности равна значению `K`, при этом карма также может принимать как положительные, так и отрицательные значения.

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер `i` он попадает к персонажу номер `i+1`, затем к персонажу номер `i+2`, и т.д. В комнате последнего персонажа с номером `N` портала к другому персонажу нет.

Для перемещения между персонажами можно использовать еще и заклинания телепортации, но к сожалению у героя осталось всего лишь два свитка с заклинаниями. Поэтому один из этих свитков придется использовать для того, чтобы телепортироваться к любому из персонажей, а второй свиток – чтобы покинуть игровой мир, после того, как карма героя станет равна `K`.

Помогите игроку определить, в какую комнату надо телепортироваться в начале и из какой комнаты нужно покинуть игровой мир, чтобы достичь кармы `K` или сообщите, что это невозможно.

В первой строке ввода записаны два числа: количество персонажей `N` (`1\ ≤\ N\ ≤\ 200\ 000`) и необходимый уровень кармы `K` (`|K|≤\ 10^9`, `K≠0`). Во второй строке через пробел записаны `N` целых чисел `a_1`, `a_2`, …, `a_N` – величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, …, `N` соответственно.

Выведите номер комнаты, в которую надо войти игроку и номер комнаты, из которой надо выйти, чтобы набрать карму `K`. Если возможных вариантов несколько, то необходимо вывести самый короткий путь, а если и таких несколько, то путь, начинающийся в комнате с как можно большим номером. Если достичь кармы `K` последовательно общаясь с персонажами невозможно, то выведите одно число `-1`.

5 3
-2 2 -1 2 4

2 4

7 1
1 -1 1 -1 1 -1 2

5 5

4 3
2 2 2 2

-1