Problem B
Beautiful Subarrays

The Great Lord Pooty has an array of numbers $A$ and a special number $K$. $A$ is $0$-indexed, i.e. the first element has index $0$, the second has index $1$, and so on. By decree, he defined the beauty of a subarray as the sum of its value minus $K$ multiplied by its length. Formally, for some integers $0 \le L \le R \le N - 1$, if we have the subarray $A[L \dots R]$, we define $\text {Beauty}(L, R) = \sum ^ R_ L (A_ i) - (R - L + 1) \times K$.

Today, he wants to find a subarray with some beauty $B$. As such it falls to you, his humble servant, to find such a subarray if it exists, or face his eternal wrath.

Input

The first line contains three integers, $N (1 \leq N \leq 200\, 000)$, $K (0 \leq K \leq 200\, 000)$ and $B(-10^{13} \leq B \leq 10^{13})$. The second line prints the $0$-based indexed array $A$ which is given by $N$ integers $(-200\, 000 \leq A_ i \leq 200\, 000)$.

Output

If such a subarray exists, print $L$ and $R$, the leftmost and rightmost index of the subarray, else print $-1$. If multiple subarray exist, print the smallest $(L, R)$ lexicographically. This means that we break ties by smallest $L$, followed by smallest $R$.

Subtasks

1. ($25$ Points): $N \leq 200$.

2. ($15$ Points): $N \leq 3000, K = 0$

3. ($10$ Points): $N \leq 3000$

4. ($10$ Points): $K = 0$ and for all $0 \leq i \leq N - 1$, $0 \leq A_ i$

5. ($10$ Points): For all $0 \leq i \leq N - 1$, $K \leq A_ i$

6. ($10$ Points): $K = 0$

7. ($20$ Points): No additional constraint.

Explanation

In the first sample, either $(0, 1)$, $(1, 2)$, and $(2, 3)$ are possible subarrays with beauty $B = 5$ (as $K = 0$). We print the lexicographically smallest subarray: $(0, 1)$.

In the second sample, $(1, 3)$ is the only possible subarray with beauty $B = 5$ as $A_1 + A_2 + A_3 - (3 - 1 + 1) \times K = 3+2+3 - (3-1+1) \times 1 = 8-3 = 5$.

In the third sample, there is no such a subarray, so we print $-1$.

Warning

The I/O files are large. Please use fast I/O methods.

4 0 5
3 2 3 2

0 1

4 1 5
2 3 2 3

1 3

1 3 9
13

-1