After several holiday seasons, cheesecake's old Christmas lights aren't looking too good. Some of the bulbs still glow normally, but others are almost completely out. cheesecake wants to reuse them again next year, but doesn't want his decorations to look too shabby either.

cheesecake's string of Christmas lights consists of $N$ individual bulbs. The $i^{th}$ bulb has a brightness of $A_i$. cheesecake defines the variance of a contiguous string of bulbs to be the difference in brightness between the brightest and the dimmest bulb in that string. cheesecake considers a string of bulbs to be consistent if its variance is no greater than $K$.

cheesecake wants to keep a consistent string of lights for next year, but he also wants the lights to be pretty. As both a poor judge of aesthetics and an indecisive person, he cannot choose the prettiest segment of lights. As such, he has $Q$ queries, each of the following form:

If cheesecake considers the string of lights from $l$ to $r$ $(1\le l\le r\le N)$ to be pretty, which contiguous segment of lights should he keep from $[l:r]$ such that the segment is consistent and has the maximum length possible?

Help cheesecake keep his decorations beautiful for another year!

Constraints

Subtask 1 [20%]

$1\le N\le 1000$

$0\le K,A_i\le {10}^5$

$1\le Q\le 1000$

Subtask 2 [80%]

$1\le N\le {10}^5$

$0\le K,A_i\le {10}^9$

$1\le Q\le {10}^5$

Input Specification

The first line of input will contain $N$ and $K$.

The second line will contain $N$ space-separated integers, $A_1,A_2,\dots ,A_N$, the brightness of the bulbs.

The third line will contain $Q$.

The next $Q$ lines will each contain a query in the form l r.

Output Specification

Output the answer to each query on a separate line. Each answer should be of the form a b $(l\le a\le b\le r)$, where $[a:b]$ is the maximum length consistent subarray of $[l:r]$. If there are multiple answers of the same length, output the one with the smallest values of $a$ and $b$.

Sample Input

7 4
3 6 8 4 3 6 1
3
2 6
3 6
1 3

Sample Output

2 4
4 6
1 2

Explanation for Sample Output

Note that in the first query, both 2 4 and 4 6 have the same length, but we output the smallest possible answers. Similarly, in the third query, 2 3 is the same length but not outputted.