Ґґлечики

Вхідні дані

Перший рядок містить цілі числа $n$ і $Q$ ( $1 \leq n, Q \leq 3 \cdot 1 0^{6}$ 1 \leq n, Q \leq 3 \cdot 10^6).

Другий рядок містить $n$ цілих чисел $a_{i}$ a_i, ( $2 \leq a_{i} \leq 5 \cdot 1 0^{5}$ 2 \leq a_i \leq 5 \cdot 10^5).

В наступних $Q$ рядках містяться числа $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).

Вихідні дані

В $Q$ рядках виведіть сумарну кількість літрів, що залишиться в усіх цих ґґлечиках після дії магії, для кожного з запитів.

Приклади

Приклад 1

Loading

Примітка

У першому запиті $l = 1$ l=1, $r = 3$ r=3, $k = 20$ k=20.

Розглядаємо ґґлечики з індексами від $1$ до $3$ : $a_{1} = 5$ a_1=5, $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10.

Для ґґлечика з числом $5$ : $20$ ділиться на $5$ , але не ділиться на $25$ , тому залишиться $\frac{20}{5} = 4$ \frac{20}{5}=4.

Для ґґлечика з числом $3$ : $20$ не ділиться на $3$ , тому залишиться $20$ .

Для ґґлечика з числом $10$ : $20$ ділиться на $10$ , але не ділиться на $100$ , тому залишиться $\frac{20}{10} = 2$ \frac{20}{10}=2.

Отже, відповідь на перший запит: $4 + 20 + 2 = 26$ 4+20+2=26.

У другому запиті $l = 0$ l=0, $r = 4$ r=4, $k = 12$ k=12.

Розглядаємо всі ґґлечики: $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.

Для ґґлечиків з числом $2$ : $12$ ділиться на $2^{2} = 4$ 2^2=4, але не ділиться на $2^{3} = 8$ 2^3=8, тому в кожному з них залишиться $\frac{12}{4} = 3$ \frac{12}{4}=3.

Для ґґлечика з числом $5$ : $12$ не ділиться на $5$ , тому залишиться $12$ .

Для ґґлечика з числом $3$ : $12$ ділиться на $3$ , але не ділиться на $9$ , тому залишиться $\frac{12}{3} = 4$ \frac{12}{3}=4.

Для ґґлечика з числом $10$ : $12$ не ділиться на $10$ , тому залишиться $12$ .

Отже, відповідь на другий запит: $3 + 12 + 4 + 12 + 3 = 34$ 3+12+4+12+3=34.

У третьому запиті $l = 2$ l=2, $r = 3$ r=3, $k = 100$ k=100.

Розглядаємо ґґлечики: $a_{2} = 3$ a_2=3, $a_{3} = 10$ a_3=10.

Для ґґлечика з числом $3$ : $100$ не ділиться на $3$ , тому залишиться $100$ .

Для ґґлечика з числом $10$ : $100$ ділиться на $1 0^{2} = 100$ 10^2=100, тому залишиться $\frac{100}{100} = 1$ \frac{100}{100}=1.

Отже, відповідь на третій запит: $100 + 1 = 101$ 100+1=101.

Таким чином, правильні відповіді для прикладу: $26$ , $34$ , $101$ .

Оцінювання

Підзадача $1$ ( $10$ балів) : ( $n, Q \leq 1 0^{3}$ n, Q \le 10^3)
Підзадача $2$ ( $10$ балів) : ( $a_{i} = 2$ a_i = 2)
Підзадача $3$ ( $20$ балів) : ( $a_{0} = a_{1} = a_{2} = \dots = a_{n - 1}$ a_0 = a_1 = a_2 = \ldots = a_{n - 1})
Підзадача $4$ ( $50$ балів) : ( $l_{i} = 0, r_{i} = n - 1$ l_i = 0, r_i = n - 1)
Підзадача $5$ ( $50$ балів) : (усі $a_{i}$ a_i — прості)
Підзадача $6$ ( $50$ балів) : ( $k_{0} = k_{1} = k_{2} = \dots = k_{Q - 1}$ k_0 = k_1 = k_2 = \ldots = k_{Q - 1})
Підзадача $7$ ( $50$ балів) : (усі $a_{i} = 2^{k}$ a_i = 2^k)
Підзадача $8$ ( $100$ балів) : ( $n, Q \leq 1 0^{5}$ n, Q \leq 10^5)
Підзадача $9$ ( $110$ балів) : Без додаткових обмежень