Problem Description

LJJ has a "counting book" at home, a book filled entirely with numbers, which LJJ adores. The book contains a sequence A. Each operation can increment or decrement a continuous interval by 1 and take the result modulo K (where incrementing K-1 results in 0, and decrementing 0 results in K-1). We define the harmony function F(A,K) as the minimum number of operations required to make all elements of the sequence zero.

For example, given A = {3, 3, 2, 3} and K = 4, by transforming A into {0, 0, 3, 0} and then into {0, 0, 0, 0}, the requirement is met, so F(A,K) = 2.

Now, given a sequence A of length n (n <= 200000), where A[L][R] represents the continuous subsequence from the L-th to the R-th position in sequence A. There are m (m <= 100000) queries. Each query inputs L, R, and K, and you need to find the value of F(A[L][R],K).

Note: The data guarantees that K > Max{A[1], A[2], ..., A[n]}.

Input Format

The first line contains two integers n and m, indicating the length of the sequence and the number of queries, respectively.
The second line contains n integers, where the i-th integer represents A[i].
From the third line to the (m+2)-th line, each line contains three integers L, R, and K (1 <= L <= R <= n, K <= 2^30).

Output Format

Output m lines, each containing a single integer representing the answer to each query F(A[L][R],K).

Sample Input and Output

Input Sample #1

7 2
8 8 8 0 8 8 8
1 7 9
3 5 17

Output Sample #1

2
16

Input Sample #2

4 1
5 3 8 2
1 4 9

Output Sample #2

8

Input Sample #3

10 10
7 7 6 5 5 2 8 5 0 3 
1 8 11
3 10 11
4 7 12
9 10 12
3 5 10
2 7 10
7 9 10
2 7 11
1 4 11
4 7 10

Output Sample #3

12
15
9
3
5
8
5
9
6
7

Notes

The data guarantees that for each query, K > Max{A[1], A[2], ..., A[n]}.

• 10%: n <= 10, m = 1, K <= 10
• 30%: n <= 1000, m = 1, K <= 2^30
• 50%: n <= 200000, m = 1, K <= 2^30
• Another 10%: n <= 200000, m <= 100000, K = 2
• Another 20%: n <= 30000, m <= 30000, K <= 2^30
• 100%: n <= 200000, m <= 100000, K <= 2^30

见题面 Input 部分

见题面 Output 部分