Fișierul intrare/ieșire	investitie.in, investitie.out	Sursă	OJI 2022, clasele 11-12 (OSEPI)
Autor	Mihai Bunget	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.75 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Investitie (clasele 11-12)

După o lungă activitate în domeniul instalațiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acțiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acțiuni, în M zile consecutive.

În prima zi, suma de bani investită în compania i este s(1)(i) = a(i), pentru orice i=1..N, unde valorile a(i) sunt date.

Numerele a(1), a(2), …, a(N) reprezintă o permutare a numerelor {1,2,...,N}.

În ziua a j-a el va investi în compania i o sumă de bani egală cu s(j)(i) = s(j-1)(a(i)), pentru orice zi j = 2..M și orice companie i = 1..N.

Cerință

După finalizarea planului de investiții, Dorel vrea să realizeze Q statistici referitoare la sumele investite. Fiind date Q seturi de valori zi, zf, cl, cr, el dorește să afle ce sumă a investit în perioada cuprinsă între zilele zi și zf (inclusiv acestea), la companiile cu numere de ordine cuprinse între cl și cr (inclusiv acestea).

Date de intrare

Pe prima linie a fișierului de intrare investitie.in se află numerele N și M, separate prin spațiu. Pe a doua linie se află valorile a(1), a(2), ..., a(N), separate prin spațiu. Pe a treia linie se află valoarea lui Q. Pe următoarele Q linii se află câte patru valori, zi, zf, cl, cr, separate prin spațiu.

Date de ieșire

În fișierul de ieșire investitie.out se vor afișa, pe linii diferite, sumele investite corespunzătoare fiecăreia din cele Q statistici din fișierul de intrare.

Restricții

• 1 ≤ N, Q ≤ 100.000
• 1 ≤ M ≤ 1.000.000.000
• 1 ≤ zi ≤ zf ≤ M
• 1 ≤ cl ≤ cr ≤ N
• 0 ≤ cr – cl ≤ 100
• Pentru 10 puncte, M = 1
• Pentru 20 de puncte, 1 ≤ N, M ≤ 100, 1 ≤ Q ≤ 1000
• Pentru 12 puncte, 101 ≤ N , M ≤ 3000
• Pentru 24 de puncte, 1 ≤ N ≤ 50
• Pentru 34 de puncte fără alte restricții

Mențiune

• Rezultatele evaluării pot fi diferite față de cele din concurs.

Exemplu

Explicație

Sumele investite în cele trei zile, în acțiuni ale celor opt companii, vor fi:

3 1 7 2 6 4 5 8
7 3 5 1 4 2 6 8
5 7 6 3 2 1 4 8

Prima statistică cere suma investită în prima zi în companiile cu numere de ordine de la 3 la 7. Suma este 7+2+6+4+5=24.
A doua statistică cere suma investită în primele două zile în companiile cu numerele de ordine de la 12 la 4. Suma este +(7+3+5+1)=29.
Similar se calculează celelalte statistici.