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

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

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 23 3 21 32 3

Output

    18
    9

Input

    8 62 4 8 8 8 2 4 161 82 53 42 47 73 6

Output

    256
    192
    128
    128
    16
    192

Note

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

- $$$[1;1]$$$ — $$$\operatorname{sum}[1;1] \times \operatorname{gcd}[1;1]$$$ = $$$3 \times 3$$$ = $$$9$$$;

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

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

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

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

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