SumOfAllQueries

Cerință

Se dă un vector $V$ de $N$ numere naturale. Să se proceseze $M$ operații de tipul:

• $U$ $x$ $y$: $V_x = y$
• $Q$ $x$ $y$: Să se calculeze $\sum_{i=x}^{y} \sum_{j=i}^{y} S(i, j)$, unde $S(i, j) = V_i + V_{i + 1} + \dots + V_j$

Date de intrare

Pe prima linie se găsesc numerele naturale $N$ și $M$. Pe următoare linie se găsesc $N$ numere naturale reprezentând vectorul $V$. Pe următoarele $M$ linii se găsește câte un triplet $c$ $x$ $y$, unde $c$ este un caracter din mulțimea $\{U, Q\}$, reprezentând operațiile.

Date de ieșire

Programul va afișa pe ecran rezultatele operațiilor de tip $Q$, câte unul pe un rând, în ordinea primită la intrare.

Restricții și precizări

• $1 \leq N, M \leq 250.000$
• $1 \leq x \leq N$
• $1 \leq x \leq y \leq N$, dacă $c = Q$
• $1 \leq y \leq 10^9$, dacă $c = U$
• $1 \leq V[i] \leq 10^9$
• Deoarece rezultatul operațiilor de tip $Q$ poate fi foarte mare, acesta se va calcula modulo $2^{32}$.

Exemple

Intrare

5 3
4 2 4 2 1
Q 2 5
U 3 3
Q 1 5

Ieșire

48
84