Автор витратив всі креативні навички на попередні задачі, тому в цій умові Антона мучити не будуть. Він просто дасть вам цікаву задачку.
Вам задано масив $$$a$$$, який складається з $$$n$$$ цілих чисел. Також вам задано $$$q$$$ запитів $$$[l;r]$$$. Для кожного запиту знайдіть максимальне значення $$$\operatorname{sum}[tl;tr] \times \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$$$ цілих чисел — відповіді на запити.
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
У першому прикладі є такі відрізки: