After several holiday seasons,

's old Christmas lights aren't looking too good. Some of the bulbs still glow normally, but others are almost completely out. wants to reuse them again next year, but doesn't want his decorations to look too shabby either. individual bulbs. The bulb has a brightness of . 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. considers a string of bulbs to be *consistent* if its variance is no greater than .

*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 queries, each of the following form:

If to to be pretty, which contiguous segment of lights should he keep from such that the segment is

considers the string of lights fromconsistentand has the maximum length possible?

Help

keep his decorations beautiful for another year!#### Constraints

##### Subtask 1 [20%]

##### Subtask 2 [80%]

#### Input Specification

The first line of input will contain and .

The second line will contain space-separated integers, , the brightness of the bulbs.

The third line will contain .

The next 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`

, where is the maximum length consistent subarray of . If there are multiple answers of the same length, output the one with the smallest values of and .

#### 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.

## Comments