404998: GYM101733 D Triangle Construction

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 l_i (1 ≤ l_i ≤ 10¹⁸), 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 l_i l_j l_k 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