TBATTLE - Thor vs Frost Giants


Thor is caught up in a fierce battle with Loki's army. This army consists of frost giants that have magical powers with them. Their strength levels gets multiplied when they are together. Giants are not highly skilled in the arts of combat, but their sheer size and strength make them formidable opponents even for the Asgardian gods. Thor is no exception. They recover very fast from physical injury but their recovery slows down when they are exposed to extreme heat.
Thor's hammer can generate heat only in multiples of heat quantum N. Frost giants get killed only when their combined strength level is exactly equal to the heat level of the hammer. Thor is interested in killing a continuous stretch of frost enemies with a throw of his hammer with a preference to kill closer enemies first.
Continuous stretch is defined as a set of consecutive elements.
Help Thor to determine the minimum stretch of frost giants that could be killed in a throw. In case of multiple minimal stretches, output the indices of that stretch that has lowest starting index. If there is no such continuous stretch possible then print -1.

Input

The first line will contain N, the number of Frost Giants in Loki's army and the Heat quantum.
The second line will contain N integers (a_0, a_2....., a_n-1) - the strength of each frost giant.
Minimum stretch of the army should be 1.

  • 1N100000
  • 1a_i100000

Output

Output the range of the minimum stretch of frost giants that could be killed in a throw. In case of multiple minimal stretches, output the indices of that stretch that has lowest starting index.
If there is no such continuous stretch possible then print -1.

Example

Input:
3
1 2 9

Output: 
2 2
Input: 
5
2 3 4 8 9 Output:
-1
Input:
10
2 4 3 5 17 4 7 5 2 15

Output:
7 8

Explanation

Input #1:
Thor can only kill the stretch [2,2] as this is the minimum length range with strength, multiple of 3.

Input #2:
There is no stretch of frost giants that have combined strength as a multiple of 5.

Input #3:
There are many stretches of frost giants that have strength as multiple of 10. But the minimal stretch with the least indices is from [7,8]. Minimum size stretches are [7, 8] and [8, 9]. Out of them we select [7,8].


hide comments
kesh4281: 2020-03-25 09:38:55

Focus on u want to find the "starting index of Minimum length" and that index should be smallest in case of multiple ans.

copperium: 2019-07-13 01:36:08

@optimus_v2: The answer should be 4 7 shouldn't it, that's the first time 3 2 7 8 repeats.

Soooo many off-by-one errors in this problem.

optimus_v2: 2017-06-28 10:18:15

critical case :
168
1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8 1 2 8 2 3 2 7 8

ans= 12 15 , 3*2*7*8=168 // ar[12]=3 , ar[13]=2 , ar[14]=7 , ar[15]=8 .

Main series : 1 2 8 2 3 2 7 8

rajeev_899: 2017-06-13 09:38:15

can anyone explain the test case 2

aeon: 2017-01-25 05:12:57

can anyone help me I'm getting WA at 6th test case.

Apoorv Jindal: 2013-12-27 23:55:51

@andrey maksimenko: i meant rest of the numbers to be 1s.

Andrey Maksimenko: 2013-12-14 20:40:37

Apoorv Jindal: If n=210, then should be 210 strengths, not 5.

Apoorv Jindal: 2013-12-14 14:42:00

Weak test cases! try this test case n=210 Strengths 2 3 5 7 6 1 1 1 1 1(205 1s in all). Some solutions that fail get AC too.

Last edit: 2013-12-27 23:57:24
wisfaq: 2013-11-17 06:38:24

Please remove language restrictions

:D: 2013-11-17 06:38:24

Yes, the problem still makes perfect sense with a_i=0, but I think description should reflect test cases here. We would force somewhat special cases handling out of solutions and then not even verify it. I changed the description accordingly.


Added by:BLANKRK
Date:2013-11-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Code Weavers 2013