L. Modulo Queries
time limit per test
8 s
memory limit per test
1024 MB
input
standard input
output
standard output

You are given an array $$$A$$$ of size $$$N$$$ and $$$Q$$$ queries.

In each query, you will be given three integers: $$$l$$$, $$$r$$$, and $$$x$$$. Find the value of

$$$$$$

(A_l \text{ mod } x) + (A_{l + 1} \text{ mod } x) + \dots + (A_{r - 1} \text{ mod } x) + (A_r \text{ mod } x)

$$$$$$

Note that $$$(x \text{ mod } y)$$$ denotes the remainder when $$$x$$$ is divided by $$$y$$$.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1\leq N, Q\leq 2\cdot 10^5$$$) — the length of the array and the number of queries.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1\leq A_i\leq 2\cdot 10^5$$$) — the elements of the array $$$A$$$.

Each of the next $$$Q$$$ lines contains three integers $$$l$$$, $$$r$$$, and $$$x$$$ ($$$1\leq l\leq r\leq N$$$, $$$1\leq x\leq 2\cdot 10^5$$$) — descriptions of the queries.

Output

Print $$$Q$$$ integers — the answers to the queries.

Examples
Input
7 10
14 16 9 6 9 10 16
5 6 3
2 2 7
5 7 5
4 6 4
7 7 7
7 7 16
2 6 15
6 6 12
7 7 11
3 7 2
Output
1 2 5 5 2 0 35 10 5 2
Input
7 10
8 18 6 15 4 18 15
5 7 2
1 1 18
4 5 3
3 5 12
6 7 10
5 5 14
4 4 1
4 4 19
7 7 12
6 6 4
Output
1 8 1 13 13 4 0 15 3 2
Input
7 10
14 8 8 12 7 10 15
5 5 10
1 4 5
2 4 6
2 3 17
5 6 9
3 7 15
6 6 11
7 7 10
7 7 20
2 7 17
Output
7 12 4 16 8 37 10 5 15 60
Input
7 10
11 9 18 5 11 14 10
1 7 18
3 6 4
7 7 16
4 4 5
5 6 12
4 6 16
7 7 2
2 3 5
3 7 4
2 4 19
Output
60 8 10 0 13 30 0 7 10 32