Background

Please refer to the solution article at https://www.cnblogs.com/Blog-of-Eden/p/9367521.html.

Problem Description

LJJ has a “number book” at home, which means the book contains only numbers. LJJ loves it very much.

In the number book there is a sequence $A$. In each operation, you may add $1$ or subtract $1$ to a continuous interval, and then take modulo $k$. We define the harmony function $f(A,k)$ as the minimum number of operations needed to make all elements of the sequence become $0$.

For example, when $A=\{3,3,2,3\}$ and $k=4$, by changing $A$ into $\{0,0,3,0\}$, and then changing $A$ into $\{0,0,0,0\}$, the goal can be achieved, so $f(A,k)=2$.

Now, given a sequence $A$ of length $n$, let $A_{l,r}$ denote the continuous subsequence of $A$ from position $l$ to position $r$. There are $m$ queries. Each query gives $l,r,k$. You need to compute the value of $f(A_{l,r},k)$.

Input Format

Line $1$: Two integers $n,m$, meaning the sequence length is $n$, and there are $m$ queries.

Line $2$: $n$ integers, where the $i$-th integer represents $A[i]$.

Lines $3$ to $m+2$: Each line contains three integers $l,r,k$.

Output Format

Output $m$ lines: each line contains one integer, representing the answer $f(A_{l,r},k)$ for each query.

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

2
16

4 1
5 3 8 2
1 4 9

8

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

12
15
9
3
5
8
5
9
6
7

Hint

It is guaranteed that for each query, $k>\max_{i = 1}^{n}A_i$.

For $100\%$ of the testdata: $n \le 200000$, $m \le 100000$, $k \le 2^{30}$.

Translated by ChatGPT 5