Time limit: 1s
Memory limit: 128MB
Input:
Output:
Cerință
Se dă un vector de numere naturale. Se dau de asemenea query-uri de forma , unde se cere suma tuturor subsecvențelor de elemente consecutive. Mai formal, pentru fiecare query , se cere rezultatul funcției , unde este suma tuturor elementelor din secvența .
Date de intrare
N Q
A[1] A[2] ... A[N]
L[1] R[1]
L[2] R[2]
...
L[Q] R[Q]
Date de ieșire
S[1]
S[2]
...
S[Q]
Restricții și precizări
- Se recomandă folosirea fastio.
- Deoarece răspunsurile sunt prea mari pentru a fi reprezentate de tipurile de date implicite din limbajul C++, se vor afișa modulo .
# | Punctaj | Restricții |
---|---|---|
1 | 20 | |
2 | 10 | |
3 | 20 | |
4 | 50 |
Exemplu
stdin
5 4
5 3 2 4 2
3 4
3 5
4 5
1 5
stdout
12
28
12
109
Explicație
Pentru primul query (secvența ), suma este .
Pentru al doilea query (secvența ), suma este .
Pentru al treilea query (secvența ), suma este .
Pentru al patrulea query (secvența ), suma este .