Estructures de dades (4) X67584

Donat un conjunt de números $v_0, v_1, \dots, v_{n-1}$ i una llista de preguntes, responeu-les eficientment.

Les preguntes són del tipus: donats dos números $l, r$ calculeu la suma de tots els elements $v_i$ amb $l \leq v_i \leq r$, mòdul $10^{12} + 7$. Després de cada pregunta, afegiu el resultat a la llista, de manera que les següents preguntes també consideraran els anteriors resultats.

Per exemple, suposem que tenim els números $[1, 2]$ i ens demanen calcular la suma de $l = 1, r = 2$. El resultat és $1 + 2 = 3$, i la nostre llista passa a ser $[1, 2, 3]$. Si ara ens demanen calcular la suma de $l = 2, r = 15$ el resultat seria $2 + 3 = 5$. En cas que ara ens demanessin la suma $l = 2, r = 2$ el resultat seria $2$ i, per tant, la nostra llista passaria a ser $[1,2,2,3,5]$. Si ens tornessin a demanar a suma $l = 2, r = 2$ ara el resultat seria $4$ i la llista seria $[1,2,2,3,4,5]$.

Entrada

L’entrada consisteix en diversos casos, hi ha com a molt $100$ casos. Cada cas comença amb una línia amb dos enters $1 \leq n, q \leq 5 \cdot 10^4$ - el nombre d’elements del conjunt i el nombre de preguntes. A continuació hi ha una línia amb $n$ enters $v_0, v_1, \dots, v_{n-1}$ amb $0 \leq v_i \leq 10^{12} + 7$ - els elements del conjunt.

Finalment apareixen $q$ línies, una per cada pregunta. A cada línia hi ha dos enters $0 \leq l \leq r < 10^{12} + 7$ - els extrems de l’interval del qual es vol calcular la suma.

La suma de les $n$ i la suma de les $q$ de tots els casos són ambdues menors a $5 \cdot 10^5$.

Sortida

Per a cada pregunta, calculeu la suma dels elements $v_i$ tal que $l \leq v_i \leq r$ mòdul $10^{12} + 7$, imprimint una resposta per línia.