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

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

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

• $l\le tl\le tr\le r$;

• $\mathrm{sum}[tl;tr]$ — сума усіх чисел на відрізку $[tl;tr]$;

• $\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;1]$ — $\mathrm{sum}[1;1]\times \gcd [1;1]$ = $3\times 3$ = $9$;

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

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

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

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

• $[3;3]$ — $\mathrm{sum}[3;3]\times \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$ бали): без додаткових обмежень.