Benny and Sum
Tag(s):

Algorithms, Hard, Sqrt-Decomposition

Problem
Editorial
Analytics

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.

SAMPLE INPUT
10 5
23 32 42 50 2 33 41 5 100 3
2 10 3
1 9 23
3 10 12
2 8 4
2 10 5

SAMPLE OUTPUT
11
75
36
9
13

Explanation

1. 2 + 0 + 2 + 2 + 0 + 2 + 2 + 1 + 0 = 11
2. 0 + 9 + 19 + 4 + 2 + 10 + 18 + 5 + 8 = 75
3. 6 + 2 + 2 + 9 + 5 + 5 + 4 + 3 = 36
4. 0 + 2 + 2 + 2 + 1 + 1 + 1 = 9
5. 2 + 2 + 0 + 2 + 3 + 1 + 0 + 0 + 3 = 13
Time Limit: 1.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...