New Year's '16 P7 - Old Christmas Lights

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem types

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 individual bulbs. The bulb has a brightness of . 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 .

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

If cheesecake considers the string of lights from to to be pretty, which contiguous segment of lights should he keep from such that the segment is consistent and has the maximum length possible?

Help cheesecake keep his decorations beautiful for another year!

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.