НСД, Сума, Помножити. що?...

Вхідні дані

Перший рядок містить два цілі числа $n$, $q$ (1 \le n, q \le 2 \cdot 10^5) — кількість елементів в масиві і кількість запитів відповідно.

Другий рядок містить $n$ цілих чисел a_i (1 \le a_i \le 6 \cdot 10^6) — опис масиву.

Кожен з наступних $q$ рядків містить по два цілі числа $l$, $r$ (1 \le l \le r \le n) — опис запитів.

Вихідні дані

Виведіть $q$ цілих чисел — відповіді на запити.

Приклади

Примітка

У першому прикладі є такі відрізки:

• $[1;1]$ — \operatorname{sum}[1;1] \times \operatorname{gcd}[1;1] = 3 \times 3 = $9$;

• $[1;2]$ — \operatorname{sum}[1;2] \times \operatorname{gcd}[1;2] = 6 \times 3 = $18$;

• $[1;3]$ — \operatorname{sum}[1;3] \times \operatorname{gcd}[1;3] = 8 \times 1 = $8$;

• $[2;2]$ — \operatorname{sum}[2;2] \times \operatorname{gcd}[2;2] = 3 \times 3 = $9$;

• $[2;3]$ — \operatorname{sum}[2;3] \times \operatorname{gcd}[2;3] = 5 \times 1 = $5$;

• $[3;3]$ — \operatorname{sum}[3;3] \times \operatorname{gcd}[3;3] = 2 \times 2 = $4$.

Оцінювання

1. ($4$ бали): n \le 3;

2. ($8$ балів): n, q \le 10^3;

3. ($5$ балів): n \le 10^3;

4. ($17$ балів): n, q \le 10^5;

5. ($14$ балів): n \le 10^5;

6. ($5$ балів): a_i \le 20;

7. ($7$ балів): a_i \le 10^3;

8. ($16$ балів): l = 1;

9. ($24$ бали): без додаткових обмежень.