DivPlusMinus

Lui M29 îi plac jocurile cu subsecvențe. Pentru o secvență dată, M29 îi calculează frumusețea.

Fie subsecvența $C = (c_1, c_2, \dots, c_k)$. Notăm frumusețea cu $B$.

Calculăm frumusețea adunând elementele care au în secvență un divizor (diferit de propria poziție) și scăzându-le pe cele care nu au:

Unde sumele sunt definite după indici ($i$ și $j$):

M29 și-a dat seama că nu poate calcula răspunsul pentru atât de multe subsecvențe, astfel că vă pune pe voi să o faceți.

Cerință

Se dă un șir $A$ cu $N$ elemente indexate de la $1$.
De asemenea, se dau $Q$ întrebări. Pentru fiecare întrebare, primiți două numere $l$ și $r$ și trebuie să calculați frumusețea subsecvenței $(A[l], \dots, A[r])$.

Date de intrare

Se citesc de la tastatură:

• Pe prima linie numerele $N$ și $Q$.
• Pe următoarea linie $N$ numere, elementele șirului $A$.
• Pe următoarele $Q$ linii, două valori $l$ și $r$.

Date de ieșire

Se vor afișa $Q$ linii. Pe linia $i$ se va afișa răspunsul pentru întrebarea $i$.

Restricții și precizări

• $1 \le Q \le 200\,000$
• $1 \le N \le 100\,000$
• $1 \le l \le r \le N$
• $1 \le A_i \le 1\,000\,000$

Exemplu

stdin

7 6
1 2 3 4 10 12 12
1 3
2 2
5 6
1 7
2 5
6 7

stdout

4
-2
-22
42
9
24

Explicație

1. Pentru primul query (subsecvența 1, 2, 3): Se adună 2 și 3 (pentru că ambele îl au pe 1 ca divizor) și se scade 1. Răspunsul este $2 + 3 - 1 = 4$.
2. Pentru al cincilea query: Se scad 2 și 3 și se adaugă 4 și 10 (îl au ca divizor pe 2).
3. Pentru al șaselea query: Se adaugă 12 și 12 ($A[6]$ îl are ca divizor pe $A[7]$, iar $A[7]$ îl are ca divizor pe $A[6]$).