Harmonious Sequence Operations

LJJ loves his book of numbers – the so‐called "number book" – which contains a sequence (A) of integers. In this problem, you are given an array (A) of length (n) with (0 \le A[i] < K) and a number (K) (with (K > \max(A))). An operation is defined as selecting a contiguous subarray (A[L..R]) and either adding (1) or subtracting (1) to every element in that subarray, with the result taken modulo (K) (i.e. when adding, (K-1+1) becomes (0); when subtracting, (0-1) becomes (K-1)).

Define the harmonious function (F(A, K)) as the minimum number of operations needed to turn every element of (A) into (0). For example, given (A = {3,3,2,3}) and (K = 4), it is possible to achieve (A = {0,0,0,0}) in (2) operations. (One possible way is to transform (A) into ({0,0,3,0}) in the first operation and then to ({0,0,0,0}) in the second operation.)

Now, you are given (m) queries. Each query provides three integers (L, R, K) and asks you to compute (F(A[L..R], K)) for the contiguous subarray (A[L..R]) (with 1-indexing). It can be shown that for any valid subarray (A[L..R]), the answer can be computed by the following formula:

[ F(A[L..R],K) = \frac{\min(A_L, K - A_L) + \min(A_R, K - A_R) + \sum_{i=L}^{R-1} \min(|A_{i+1} - A_i|,; K - |A_{i+1} - A_i|)}{2}. ]

You are to answer all queries.

Note: The input guarantees that (K > \max{A[1], A[2], \dots, A[n]}).

inputFormat

The first line contains two integers (n) and (m) ((1 \le n \le 200000,\ 1 \le m \le 100000)). The second line contains (n) integers (A[1], A[2], \dots, A[n]) where (0 \le A[i] < K). Each of the following (m) lines contains three integers (L, R, K) representing a query (1-indexed).

outputFormat

For each query, output an integer representing (F(A[L..R], K)), the minimum number of operations required to make all the numbers in the subarray equal to zero.

sample

4 1
3 3 2 3
1 4 4

2