Estructures de dades (4) X67584

Donat un conjunt de números v₀, v₁, …, 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 ≤ v_i ≤ r, mòdul 10¹² + 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 ≤ n, q ≤ 5 · 10⁴ - el nombre d’elements del conjunt i el nombre de preguntes. A continuació hi ha una línia amb n enters v₀, v₁, …, v_n−1 amb 0 ≤ v_i ≤ 10¹² + 7 - els elements del conjunt.

Finalment apareixen q línies, una per cada pregunta. A cada línia hi ha dos enters 0 ≤ l ≤ r < 10¹² + 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 · 10⁵.

Sortida

Per a cada pregunta, calculeu la suma dels elements v_i tal que l ≤ v_i ≤ r mòdul 10¹² + 7, imprimint una resposta per línia.