「みんなのプロコン」本選 オープンコンテスト

C - 倍数クエリ


Time limit時間制限 : 6sec / Memory limitメモリ制限 : 512MB

配点 : 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

各質問の後での数列の値は以下のようになります.

  • 1 番目の質問の後,数列は [3, 4, 4, 3, 4] になる.
  • 2 番目の質問の後,数列は [3, 4, 4, 3, 4] になる.
  • 3 番目の質問の後,数列は [3, 4, 4, 8, 9] になる.
  • 4 番目の質問の後,数列は [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

Submit提出する