Pitchers — Eolymp

Input

The first line contains integers $n$ and $Q$ ( $1 \leq n, Q \leq 3 \cdot 1 0^{6}$ 1 \leq n, Q \leq 3 \cdot 10^6).

The second line contains $n$ integers $a_{i}$ a_i ( $2 \leq a_{i} \leq 5 \cdot 1 0^{5}$ 2 \leq a_i \leq 5 \cdot 10^5).

The next $Q$ lines contain the numbers $l_{i}$ l_i, $r_{i}$ r_i, $k_{i}$ k_i ( $1 \leq k \leq 5 \cdot 1 0^{5}$ 1 \leq k \leq 5 \cdot 10^5), ( $0 \leq l \leq r < n$ 0 \leq l \leq r < n).

Output

In $Q$ lines, output the total number of liters that will remain in all these pitchers after the magic is applied, for each query.

Examples

Example 1

Loading

Note

In the first query, $l = 1$ l=1, $r = 3$ r=3, $k = 20$ k=20.

We consider the jugs with indices from $1$ to $3$ : $a_{1} = 5$ a_1=5, $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10.

For the jug with number $5$ : $20$ is divisible by $5$ , but not divisible by $25$ , so $\frac{20}{5} = 4$ \frac{20}{5}=4 will remain.

For the jug with number $3$ : $20$ is not divisible by $3$ , so $20$ will remain.

For the jug with number $10$ : $20$ is divisible by $10$ , but not divisible by $100$ , so $\frac{20}{10} = 2$ \frac{20}{10}=2 will remain.

Therefore, the answer to the first query is $4 + 20 + 2 = 26$ 4+20+2=26.

In the second query, $l = 0$ l=0, $r = 4$ r=4, $k = 12$ k=12.

We consider all jugs: $a_{0} = 2$ a_0=2, $a_{1} = 5$ a_1=5, $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10, $a_{4} = 2$ a_4=2.

For the jugs with number $2$ : $12$ is divisible by $2^{2} = 4$ 2^2=4, but not divisible by $2^{3} = 8$ 2^3=8, so $\frac{12}{4} = 3$ \frac{12}{4}=3 will remain in each of them.

For the jug with number $5$ : $12$ is not divisible by $5$ , so $12$ will remain.

For the jug with number $3$ : $12$ is divisible by $3$ , but not divisible by $9$ , so $\frac{12}{3} = 4$ \frac{12}{3}=4 will remain.

For the jug with number $10$ : $12$ is not divisible by $10$ , so $12$ will remain.

Therefore, the answer to the second query is $3 + 12 + 4 + 12 + 3 = 34$ 3+12+4+12+3=34.

In the third query, $l = 2$ l=2, $r = 3$ r=3, $k = 100$ k=100.

We consider the jugs: $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10.

For the jug with number $3$ : $100$ is not divisible by $3$ , so $100$ will remain.

For the jug with number $10$ : $100$ is divisible by $1 0^{2} = 100$ 10^2=100, so $\frac{100}{100} = 1$ \frac{100}{100}=1 will remain.

Therefore, the answer to the third query is $100 + 1 = 101$ 100+1=101.

Thus, the correct answers for the example are $26$ , $34$ , $101$ .

Scoring

Subtask $1$ ( $10$ points): ( $n, Q \leq 1 0^{3}$ n, Q \le 10^3)
Subtask $2$ ( $10$ points): ( $a_{i} = 2$ a_i = 2)
Subtask $3$ ( $20$ points): ( $a_{0} = a_{1} = a_{2} = \dots = a_{n - 1}$ a_0 = a_1 = a_2 = \ldots = a_{n - 1})
Subtask $4$ ( $50$ points): ( $l_{i} = 0, r_{i} = n - 1$ l_i = 0, r_i = n - 1)
Subtask $5$ ( $50$ points): (all $a_{i}$ a_i are prime)
Subtask $6$ ( $50$ points): ( $k_{0} = k_{1} = k_{2} = \dots = k_{Q - 1}$ k_0 = k_1 = k_2 = \ldots = k_{Q - 1})
Subtask $7$ ( $50$ points): (all $a_{i} = 2^{k}$ a_i = 2^k)
Subtask $8$ ( $100$ points): ( $n, Q \leq 1 0^{5}$ n, Q \leq 10^5)
Subtask $9$ ( $110$ points): Without additional constraints