問題文

高橋君は，数列 [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 は整数

入力例 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