P4846 LJJ Loves a Number Book

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

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)$.

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 $m$ lines: each line contains one integer, representing the answer $f(A_{l,r},k)$ for each query.

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