406474: GYM102419 G Large array

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.

The 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}$$$.

For 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$$$.

2
3 5 0
1 1 -3
5 5 10
1 1 1 2 2

0 3
-1