Probably, you have already guessed that Benny really likes different types of queries.
Sometimes she goes for a walk with her friends, sometimes goes to the cinema. But all the time she goes somewhere she can not relax if homework was not made.
She kindly asks you to help her with her homework again.
In this problem you are given an array p consisting of n elements.
You have to answer m queries.
Each query has the following format: l r x. The answer to the query is \(\sum\limits_{i=l}^{r} (p_i \bmod x)\).
For each query output the answer in a single line.
Input format
The first line contains two integers n and m.
The second line contains n integers \(p_i\) .
The next $m$ lines contain three integers each: l, r and x.
Constraints
\(1 \le n, m \le 2 \cdot 10^5\)
\(0 \le p_i \le 2 \cdot 10^5\)
\(1 \le l \le r \le n\)
\(1 \le x \le 2 \cdot 10^5\)
Output format
For each query output the answer as a single integer.
Answer for each query:
- 2 + 0 + 2 + 2 + 0 + 2 + 2 + 1 + 0 = 11
- 0 + 9 + 19 + 4 + 2 + 10 + 18 + 5 + 8 = 75
- 6 + 2 + 2 + 9 + 5 + 5 + 4 + 3 = 36
- 0 + 2 + 2 + 2 + 1 + 1 + 1 = 9
- 2 + 2 + 0 + 2 + 3 + 1 + 0 + 0 + 3 = 13
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor