406474: GYM102419 G Large array
Description
You are given an array $$$b$$$ of size $$$m$$$.
An array $$$a$$$ of size $$$n$$$ is built from $$$b$$$ by the following formula:
for every $$$i$$$ $$$(0 \leq i < n)$$$ $$$a[i] = b[i$$$ $$$mod$$$ $$$m]$$$.
You should find a sub-array from the array $$$a$$$ with a sum equal to $$$k$$$ and minimum possible size.
The arrays are 0 indexed.
InputThe first line of input contains one integer $$$t$$$ which is the number of test cases.
For every test case :
The First line contains three integers $$$m$$$ $$$n$$$ $$$k$$$, which are the size of array $$$b$$$ and the size of array $$$a$$$ and the needed sum $$$(1 \leq m \leq 10 ^ {5})$$$ $$$(m \leq n \leq 10 ^ {9})$$$ $$$(-10^{18} \leq k \leq 10^{18})$$$.
The second line contains $$$m$$$ integers, the $$$i_{th}$$$ one is $$$b_i$$$ $$$(-10^{9} \leq b_i \leq 10 ^{9})$$$, which is the $$$i_{th}$$$ element in array $$$b$$$.
it is guaranteed that the sum of $$$m$$$ between all test cases will not exceed $$$3 \times 10^{5}$$$.
OutputFor every test case : If there is no sub-array of sum $$$k$$$ print $$$-1$$$ on a line.
Otherwise print two integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$ which is a sub-array with minimal possible size and sum equal to $$$k$$$.
If there is more than one answer print the sub-array with minimum possible $$$l$$$.
ExampleInput2 3 5 0 1 1 -3 5 5 10 1 1 1 2 2Output
0 3 -1