LNKO, Összeg, Szorzat. Mi?...

Bemenet

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.

Kimenet

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

Példák

Megjegyzés

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$.

Pontozás

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.