Pixel Vision Line Reconstruction

Prof. Pang has an extraordinary vision: he can see the pixels on a 4K monitor. To test his vision, Prof. Shou displays several pixels and asks Prof. Pang to guess a straight line that contains these pixels. Formally, given k pixels with coordinates \((i, y_i)\) for \(0 \le i 0\)) representing the line \[ y = \frac{ax+b}{c}, \] such that for all \(0 \le i

[ y_i = \left\lfloor \frac{ai+b}{c} \right\rfloor. ]

Prof. Shou will ask multiple questions. He has a fixed array \(x_1, x_2, \dots, x_n\). For each question, he chooses an interval \(x_l, x_{l+1}, \dots, x_r\). Then he defines \(y_i=x_{l+i}\) for \(0 \le i \le r-l\) and asks Prof. Pang to find the parameters \(a, b, c\) for the line that satisfies

[ y_i = \left\lfloor \frac{ai+b}{c} \right\rfloor \quad (\text{for } 0 \le i \le r-l). ]

For each query, output the answer with the minimum triple \((c, a, b)\) in lexicographical order (first minimizing \(c\), then \(a\), then \(b\)). It is guaranteed that when using the whole array \(x_1, x_2, \dots, x_n\) as the query, an answer exists. Thus an answer always exists for every subarray query.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\), the number of elements in the array and the number of queries.

The second line contains \(n\) integers \(x_1, x_2, \dots, x_n\) representing the array. It is guaranteed that these numbers are such that an answer exists when considering the whole array.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) \((1 \le l \le r \le n)\) representing a query. For the query, the segment \(x_l, x_{l+1}, \dots, x_r\) is used, and the corresponding pixels are \((0, x_l), (1, x_{l+1}), \dots, (r-l, x_r)\).

outputFormat

For each query, output three integers \(c\), \(a\) and \(b\) separated by spaces in one line representing the parameters of the line.

sample

5 3
0 1 2 3 4
1 5
2 4
3 3

1 1 0
1 1 1
1 0 2