AT_yahoo_procon2017_final_c 倍数クエリ

高桥君有一个长度为 $ N $ 的数组 $ [A_1,A_2,\dots, A_N] $，他喜欢在数组一段区间内的数字都加上相同的值，而他也喜欢 $ M $ 的倍数，所以他想看看出现在数组一段区间内的 $ M $ 的倍数有哪些。 共 $ Q $ 个问题，在第 $ i $ 个问题中，有 $ l_i $，$ r_i $，$d_i$ 3个数。首先，将 $ A_{l_i},A_{l_i+1},\dots,A_{r_i} $ 各自的值加上 $ d_i $ 。然后，回答 $ A_{l_i},A_{l_i+1},\dots,A_{r_i} $ 中 $ M $ 的倍数的个数。

输入以下面的格式由标准输入提供。 $ N $ $ M $ $ Q $\ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $\ $ l_1 $ $ r_1 $ $ d_1 $\ $ l_2 $ $ r_2 $ $ d_2 $\ $ \vdots $\ $ l_Q $ $ r_Q $ $ d_Q $

共 $ i $ 行，输出第 $ i $ 个问题的答案。

- $ 1 \le N,Q,M \le 10^5 $ - $ 0 \le A_i \le 10^9 $ - $ 1 \le l_i \le r_i \le N $ - $ 0 \le d_i \le 10^9 $ - $ A_i,d_i $ 为整数 **样例1解释** 各问题后的数列值如下。 第一个问题后，数列是 $ [3,4,4,3,4] $。 第二个问题后，数列是 $ [3,4,4,3,4] $。 第三个问题后，数列是 $ [3,4,4,8,9] $。 第四个问题后，数列是 $ [6,7,7,11,12] $。