P4846 LJJ爱数书

题解请查看 [https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)。

LJJ 的家里有一本“数书”，也就是说里面全都是数字的书，LJJ 十分喜爱它。 数书里有一个序列 $A$，每次操作可以使一段连续的区间加 $1$ 或减 $1$ 并对 $k$ 取模，我们定义和谐函数 $f (A,k)$ 表示最少的操作次数，使得序列的所有元素都变为 $0$。 例如 $A=\{3,3,2,3\}$，$k= 4$ 时，通过把 $a$ 变成 $\{0,0,3,0\}$，再把 $a$ 变成 $\{0,0,0,0\}$ 就能达到要求，所以 $f(A,k)=2$。 现在，输入长度为 $n$ 的序列 $A$，设 $A_{l,r}$ 表示序列 $A$ 第 $l$ 个位置到第 $r$ 个位置的连续子序列。 有 $m$ 次询问，每次询问输入 $l,r,k$，求 $f (A_{l,r},k)$ 的值。

第 $1$ 行：两个整数 $n,m$，表示序列长度为 $n$，有 $m$ 次询问。 第 $2$ 行：$n$ 个整数，第i个整数表示 $A[i]$ 第 $3$ 至 $m+2$ 行：每行三个整数 $l,r,k$。

共 $m$ 行：每行一个整数，表示每组询问的答案 $f(A_{l,r},k)$。

数据保证每组询问的 $k>\max_{i = 1}^{n}A_i$。 对于 $100%$ 的数据：$n \le 200000$，$m \le 100000$，$k \le 2^{30}$。