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.