LNKO, Összeg, Szorzat. Mi?...
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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

Scoring

  1. ($$$4$$$ pont): $$$n \le 3$$$;
  2. ($$$8$$$ pont): $$$n, q \le 10^3$$$;
  3. ($$$5$$$ pont): $$$n \le 10^3$$$;
  4. ($$$17$$$ pont): $$$n, q \le 10^5$$$;
  5. ($$$14$$$ pont): $$$n \le 10^5$$$;
  6. ($$$5$$$ pont): $$$a_i \le 20$$$;
  7. ($$$7$$$ pont): $$$a_i \le 10^3$$$;
  8. ($$$16$$$ pont): $$$l = 1$$$;
  9. ($$$24$$$ pont): nincsenek további korlátozások.

Examples

Input
3 2
3 3 2
1 3
2 3
Output
18
9
Input
8 6
2 4 8 8 8 2 4 16
1 8
2 5
3 4
2 4
7 7
3 6
Output
256
192
128
128
16
192

Note

Az első példában a következő szegmensek vannak: