Problem Description

Takahashi has a sequence \[$ A_1,\ A_2,\ ...,\ A_N $\]. He likes to add the same value to all numbers in a certain interval of the sequence. Also, Takahashi likes multiples of \( M \), so he is interested in the number of multiples of \( M \) that appear in a certain interval of the sequence.

Please help Takahashi by answering the following questions. There will be a total of \( Q \) queries.

• In the \( i \)-th query, \( l_i,\ r_i,\ d_i \) are given. First, add \( d_i \) to each value in \( A_{l_i},\ A_{l_i\ +\ 1},\ ...,\ A_{r_i} \). Then, answer the number of multiples of \( M \) in \( A_{l_i},\ A_{l_i\ +\ 1},\ ...,\ A_{r_i} \).

Input Format

The input is given from the standard input in the following format.

$ 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 $

Output Format

Output the answer for the \( i \)-th query on the \( i \)-th line.

Sample Input and Output

Sample Input #1

5 4 4
1 2 4 3 4
1 2 2
2 5 0
4 5 5
1 5 3

Sample Output #1

1
3
1
1

Sample Input #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

Sample Output #2

3
1
0
1
3
1
2
4
0

Notes/Hints

Constraints

• $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$ are integers

Sample Explanation 1

The sequence values after each query are as follows:
- After the 1st query, the sequence becomes \\[$ 3,\ 4,\ 4,\ 3,\ 4 $\\\].
- After the 2nd query, the sequence remains \\[$ 3,\ 4,\ 4,\ 3,\ 4 $\\\].
- After the 3rd query, the sequence becomes \\[$ 3,\ 4,\ 4,\ 8,\ 9 $\\\].
- After the 4th query, the sequence becomes \\[$ 6,\ 7,\ 7,\ 11,\ 12 $\\\].

见题面 Input 部分

见题面 Output 部分