Little Andrey wants to work in IT. He already knows that he should exercise in mathematics and algorithms.
Andrey likes to play with a set of wooden sticks of various lengths. Experimentally he found that three sticks can form a triangle, if the length of the longest of them is strictly less than the sum of two others.
A sequence of n sticks is located on the table. Andrey chooses some interval with indices from l to r and looks for three sticks which can form a triangle.
Help Andrew, for each of the q intervals find three sticks such that he can make a triangle.
The first input line contains two integers n and q (1 ≤ n, q ≤ 300 000), number of sticks and number of intervals. The second line contains n integers li (1 ≤ li ≤ 1018), the array of sticks length in the order they lie on the table.
Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ n), the interval boundaries.
For each interval print any three different indices i j k (l ≤ i, j, k ≤ r) such that sticks with lengths li lj lk make a triangle. If there are no such indices, output the only number - 1.
5 3
1 3 1 3 1
1 3
2 4
1 5
-1
2 3 4
1 3 5
9 3
3 4 5 3 4 7 3 4 8
1 3
4 6
7 9
1 2 3
-1
-1
5 2
1 2 3 4 5
1 1
2 3
-1
-1
