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

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

Вам задано масив $$$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$$$ цілих чисел — відповіді на запити.

Система оцінки

  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 2
3 3 2
1 3
2 3
Вихідні дані
18
9
Вхідні дані
8 6
2 4 8 8 8 2 4 16
1 8
2 5
3 4
2 4
7 7
3 6
Вихідні дані
256
192
128
128
16
192

Пояснення

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