AT_yahoo_procon2017_final_c 倍数クエリ

[problemUrl]: https://atcoder.jp/contests/yahoo-procon2017-final/tasks/yahoo_procon2017_final_c 高橋君は，数列 \[$ 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 $ の倍数の個数を答える．

入力は以下の形式で標準入力から与えられる． > $ 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\ \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 $ は整数 ### Sample Explanation 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 $\\\] になる．