\begin{problem}{НСД, Сума, Помножити. що?...}{standard input}{standard output}{3 seconds}{256 megabytes}

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

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

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

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

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

\InputFile
Перший рядок містить два цілі числа $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$) --- опис запитів.

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

\Scoring
\begin{enumerate}
\item ($4$ бали): $n \le 3$;
\item ($8$ балів): $n, q \le 10^3$;
\item ($5$ балів): $n \le 10^3$;
\item ($17$ балів): $n, q \le 10^5$;
\item ($14$ балів): $n \le 10^5$;
\item ($5$ балів): $a_i \le 20$;
\item ($7$ балів): $a_i \le 10^3$;
\item ($16$ балів): $l = 1$;
\item ($24$ бали): без додаткових обмежень.
\end{enumerate}

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\end{example}

\Note
У першому прикладі є такі відрізки:
\begin{itemize}
\item $[1;1]$ --- $\operatorname{sum}[1;1] \times \operatorname{gcd}[1;1]$ = $3 \times 3$ = $9$;

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

\item $[1;3]$ --- $\operatorname{sum}[1;3] \times \operatorname{gcd}[1;3]$ = $8 \times 1$ = $8$;

\item $[2;2]$ --- $\operatorname{sum}[2;2] \times \operatorname{gcd}[2;2]$ = $3 \times 3$ = $9$;

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

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

\end{itemize}

\end{problem}

