#6484. LJJ 爱数书

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 284914869

题目描述

LJJ 的家里有一本「数书」,也就是说里面全都是数字的书,LJJ 十分喜爱它。

数书里有一个序列 A ,每次操作可以使一段连续的区间加 1 或减 1 并对 K 取模( K-1 1 后变为 0 0 1 后变为 K-1 ),我们定义和谐函数 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) 的值。

输入格式

第一行两个整数 n,m ,表示序列长度为 n ,有 m 次询问;
第二行有 n 个整数,第 i 个整数表示 A_i
第三至第 m+2 行,每行三个整数 l,r,K

输出格式

m 行,每行一个整数,表示每组询问的答案。

样例

样例输入 1

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

样例输出 1

2
16

样例输入 2

4 1
5 3 8 2
1 4 9

样例输出 2

8

样例输入 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

样例输出 3

12
15
9
3
5
8
5
9
6
7

数据范围与提示

对于 10\% 的数据, n\le 10,m=1,K\le 10
对于 30\% 的数据, n\le 1000,m=1,K\le 2^{30}
对于 50\% 的数据, n\le 2\times 10^5,m=1,K\le 2^{30}
另有 10\% 的数据, n\le 2\times 10^5,m\le 10^5,K=2
另有 20\% 的数据, n,m\le 3\times 10^4,K\le 2^{30}
对于全部数据, 1\le n\le 2\times 10^5,1\le m\le 10^5,K\le 2^{30},1\le l\le r\le n ,保证 K\gt \max \{A_1,A_2,\cdots ,A_n\}