\begin{problem}{LNKO, Összeg, Szorzat. Mi?...}{standard input}{standard output}{3 seconds}{256 megabytes}

Az író kimerítette minden kreatív készségét az előző problémákon, így Anton ebben a leírásban nem lesz kínozva. Csak egy érdekes problémát fog adni neked.

Adott egy $n$ elemű $a$ tömb. Továbbá adott $q$ lekérdezés $[l;r]$. Minden lekérdezéshez keressük meg a $\operatorname{sum}[tl;tr] \times \operatorname{gcd}[tl;tr]$ maximális értékét az összes ($tl;tr$) pár esetében, ahol 

\begin{itemize}
\item $l \le tl \le tr \le r$;
\item $\operatorname{sum}[tl;tr]$ --- az összes szám összege a $[tl;tr]$ szegmensben;
\item $\operatorname{gcd}[tl;tr]$ --- az összes szám legnagyobb közös osztója a $[tl;tr]$ szegmensben.
\end{itemize}

Két szám legnagyobb közös osztója $a$ $b$ a legnagyobb pozitív egész szám  $x$, ami osztható mind $a$-val, mind $b$-vel.

Egy halmaz legnagyobb közös osztója a legnagyobb pozitív egész szám $x$, ami osztható a halmaz minden elemével.

\InputFile
Az első sor két egész számot tartalmaz, $n$, $q$ ($1 \le n, q \le 2 \cdot 10^5$) --- a tömb elemeinek száma és a lekérdezések száma.

A második sor $n$ egész számot tartalmaz, $a_i$ ($1 \le a_i \le 6 \cdot 10^6$) --- a tömb leírása.

Minden következő $q$ sor két egész számot tartalmaz, $l$, $r$ ($1 \le l \le r \le n$) --- a lekérdezések leírása.

\OutputFile
Nyomtass ki $q$ egész számot --- a lekérdezések válaszait.

\Scoring
\begin{enumerate}
\item ($4$ pont): $n \le 3$;
\item ($8$ pont): $n, q \le 10^3$;
\item ($5$ pont): $n \le 10^3$;
\item ($17$ pont): $n, q \le 10^5$;
\item ($14$ pont): $n \le 10^5$;
\item ($5$ pont): $a_i \le 20$;
\item ($7$ pont): $a_i \le 10^3$;
\item ($16$ pont): $l = 1$;
\item ($24$ pont): nincsenek további korlátozások.
\end{enumerate}

\Examples

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

\Note
Az első példában a következő szegmensek vannak:
\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}

