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
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.
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.
Nyomtass ki $$$q$$$ egész számot — a lekérdezések válaszait.
3 23 3 21 32 3
18 9
8 62 4 8 8 8 2 4 161 82 53 42 47 73 6
256 192 128 128 16 192
Az első példában a következő szegmensek vannak: