НСД, Сума, Помножити. що?...
ліміт часу на тест
3 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Автор витратив всі креативні навички на попередні задачі, тому в цій умові Антона мучити не будуть. Він просто дасть вам цікаву задачку.

Вам задано масив $$$a$$$, який складається з $$$n$$$ цілих чисел. Також вам задано $$$q$$$ запитів $$$[l;r]$$$. Для кожного запиту знайдіть максимальне значення $$$\operatorname{sum}[tl;tr] \times \operatorname{gcd}[tl;tr]$$$ по всім парам ($$$tl;tr$$$), де

- $$$l \le tl \le tr \le r$$$;
- $$$\operatorname{sum}[tl;tr]$$$ — сума усіх чисел на відрізку $$$[tl;tr]$$$;
- $$$\operatorname{gcd}[tl;tr]$$$ — найбільший спільний дільник усіх чисел на відрізку $$$[tl;tr]$$$.

Найбільший спільний дільник двох чисел $$$a$$$ та $$$b$$$ — це найбільше ціле число $$$x$$$, що ділить одночасно $$$a$$$ і $$$b$$$.

Найбільший спільний дільник множини чисел — це найбільше ціле число $$$x$$$, що ділить всі елементи множини.

Вхідні дані

Перший рядок містить два цілі числа $$$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. ($$$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$$$ бали): без додаткових обмежень.

Приклади

Вхідні дані

    3 23 3 21 32 3

Вихідні дані

    18
    9

Вхідні дані

    8 62 4 8 8 8 2 4 161 82 53 42 47 73 6

Вихідні дані

    256
    192
    128
    128
    16
    192

Пояснення

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

- $$$[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$$$.