Олимпиадный тренинг

Задача 34879. K-quest


In one of the computer quest games there is the following task. There are N characters on the map of the game world, each of which the player can meet. From communication with the i-th character, the player's karma changes by the value ai, which can be either positive or negative or even zero.

Initially, the player's karma is zero. In order to pass to the next level, you need to have karma exactly equal to the value of K, while karma can also take both positive and negative values.

The rooms where the characters are located are connected by one-way magical portals, so the player will have to meet the characters in a certain sequence: after the character number i, he gets to the character number i + 1, then to the character number i + 2, and so on. .d. There is no portal to another character in the room of the last character with number N.

To move between characters, you can also use teleportation spells, but unfortunately the hero has only two scrolls with spells left. Therefore, one of these scrolls will have to be used in order to teleport to any of the characters, and the second scroll — to leave the game world after the hero's karma reaches K.

Help the player determine which room to teleport to at the beginning and which room to leave the game world to reach Karma K, or tell them it's not possible.

Input
The first line of the input contains two numbers: the number of characters N and the required level of karma K (|K| ≤ 109, K ≠ 0). The second line contains N space-separated integers a1, a2, ..., aN — values ​​by which the hero's karma changes after communicating with characters with numbers 1, 2, ..., N, respectively.

Imprint
Print the number of the room the player must enter and the number of the room from which the player must exit in order to collect karma K. big number. If it is impossible to achieve karma K by consistently communicating with the characters, then print a single number  - 1.
 
Input Output
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