Sume și progresii

Într-un univers paralel, Gigel este un olimpic intergalactic la informatică. El tocmai ce a învățat de la profesorul lui de matematică ce sunt progresiile aritmetice. Fiind curios din fire, el se întreabă cum poate folosi acest concept pentru a rezolva probleme de informatică. Astfel, el definește următoarele tipuri de operații pentru un șir de valori $a_1$, $a_2$, $a_3$, ... $a_n$.

1. Sumă pe interval: Dându-se două poziții $i$ și $j$ se calculează: $S = a_i + a_{i+1} + a_{i+2} + ... + a_j$.
2. Progresie pe interval: Dându-se două poziții $i$ și $j$ se calculează: $P = 1 \cdot a_i + 2 \cdot a_{i+1} + 3 \cdot a_{i+2} + ... + (j - i + 1) \cdot a_j$.

Cerință

Gigel vă provoacă să aplicați una dintre operațiile definite de el pentru mai multe intervale de poziții dintr-un șir dat. Puteți răspunde la toate interogările rapid și corect?

Date de intrare

Prima linie a fișierului de intrare sume_progresii.in va conține trei numere naturale $C$, $N$ și $Q$, unde $C$ reprezintă tipul de operație care trebuie aplicat, $N$ reprezintă lungimea șirului de valori, iar $Q$ reprezintă numărul de intervale pe care va trebui aplicată operația. Pe a doua linie se găsesc $N$ numere, reprezentând valorile numerelor din șir. Pe următoarele $Q$ linii vor apărea câte două valori $i$ și $j$, capetele intervalului pe care se aplică operația.

Date de ieșire

În fișierul de ieșire sume_progresii.out se vor scrie $Q$ linii, unde pe linia $i$ se va afla rezultatul operației pentru al $i$-lea interval.

Restricții și precizări

• $1 \leq C \leq 2$
• $1 \leq N, Q \leq 1 \ 000 \ 000$
• Valorile elementelor din șir vor fi cuprinse între $0$ și $1 \ 000 \ 000$.
• Se garantează că $1 \leq i \leq j \leq N$, oricare ar fi $i$ și $j$ capete de interval.

• Pentru 20 de puncte, $C = 1$ și $1 \leq N, Q \leq 1 \ 000$
• Pentru alte 20 de puncte, $C = 1$ și $1 \leq N, Q \leq 1 \ 000 \ 000$
• Pentru alte 20 de puncte, $C = 2$ și $1 \leq N, Q \leq 1 \ 000$
• Pentru alte 40 de puncte, $C = 2$ și $1 \leq N, Q \leq 1 \ 000 \ 000$

Exemplul 1

sume_progresii.in

1 5 4
15 23 41 22 9
1 1
2 3
1 5
3 5

sume_progresii.out

15
64
110
72

Explicație

Tipul de operație cerut este de sumă pe interval. Astfel, $S_1 = 15$, $S_2 = 23 + 41 = 64$, $S_3 = 15 + 23 + 41 + 22 + 9 = 110$ și $S_4 = 41 + 22 + 9 = 72$.

Exemplul 2

sume_progresii.in

2 5 4
15 23 41 22 9
1 1
2 3
1 5
3 5

sume_progresii.out

15
105
317
112

Explicație

Tipul de operație cerut este de progresie pe interval. Astfel, $P_1 = 1 \cdot 15 = 15$, $P_2 = 1 \cdot 23 + 2 \cdot 41 = 23 + 82 = 105$, $P_3 = 1 \cdot 15 + 2 \cdot 23 + 3 \cdot 41 + 4 \cdot 22 + 5 \cdot 9 = 15 + 46 + 123 + 88 + 45 = 317$ și $P_4 = 1 \cdot 41 + 2 \cdot 22 + 3 \cdot 9 = 41 + 44 + 27 = 112$.