配点 : 1000 点
問題文
高桥君有一个数列 [A_1, A_2, ..., A_N]。 高桥君喜欢对数列的某个区间内的所有数加上相同的数值。此外,高桥君喜欢 M 的倍数,所以在数列的某个区间出现的 M 的倍数的个数感到好奇。 为了高桥君
,请回答如下问题。不过,假设问题总共有 Q 个。 在第
- i 个问题中,l_i, r_i, d_i 被给出。首先,A_{l_i}, A_{l_i + 1}, ..., A_{r_i} 对每一个值 d_i 加上。然后,A_{l_i}, A_{l_i + 1}, ..., A_{r_i} 中 M 的倍数的个数是多少。
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq A_i \leq 10^9
- 1 \leq l_i \leq r_i \leq N
- 0 \leq d_i \leq 10^9
- A_i, d_i 是一个整数
入力
输入是按以下格式从标准输入给出的。
N M Q A_1 A_2 ... A_N l_1 r_1 d_1 l_2 r_2 d_2 : l_Q r_Q d_Q
出力
i 行中, 请输出第i 输出第几题的答案。
入力例 1
5 4 4 1 2 4 3 4 1 2 2 2 5 0 4 5 5 1 5 3
出力例 1
1 3 1 1
每题之后的数列值如下。
- 第一题之后,数列是 [3, 4, 4, 3, 4] 变成.
- 在第二个问题之后,数列为 [3, 4, 4, 3, 4] 变成.
- 在第三个问题之后,数列为 [3, 4, 4, 8, 9] 变成.
- 在第四个问题之后,数列为 [6, 7, 7, 11, 12] 变成.
入力例 2
10 7 9 6 10 6 10 3 8 1 8 7 2 1 9 6 3 4 9 8 9 6 3 6 3 1 9 9 1 3 7 2 6 2 1 10 0 8 9 4
出力例 2
3 1 0 1 3 1 2 4 0