QMaxT

Cerință

Se dă un vector $A$ cu $N$ elemente numere naturale. Să se răspundă la $Q$ întrebări de forma:

• $x$ $y$ $t$: cu cât este egal $ \displaystyle\sum\limits_{i=x}^{y}min(A_i, t)$?

Date de intrare

Pe prima linie a fișierului qmaxt.in se găsesc numerele $N$ și $Q$. Pe următoarea linie se găsesc $N$ numere naturale, separate printr-un spațiu, reprezentând vectorul $A$. Pe următoarele $Q$ linii se găsesc câte trei numere $x$, $y$, $t$ separate printr-un spațiu, reprezentând întrebările.

Date de ieșire

Programul va afișa în fișerul qmaxt.out $Q$ linii, pe linia $i$ aflându-se răspunsul la întrebarea $i$.

Restricții și precizări

• $1 \leq N, Q \leq 2.5 * 10^5$
• $1 \leq A_i, t \leq 10^9$
• $1 \leq x \leq y \leq N$

Exemple

qmaxt.in

10 5
7 6 5 10 10 7 7 8 10 8
8 9 9
2 10 4
5 10 1
1 4 6
4 6 2

qmaxt.out

17
36
6
23
6