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.