Dr. Henri is working on a new method of analyzing lab data! He has collected ~N~ data points: ~A_1, A_2, \dots, A_N~, and has defined the ~k~-interest of a subarray as the sum of all numbers greater than or equal to ~k~ minus the sum of all numbers less than ~k~.

For example, the ~5~-interest of the array ~[4, 2, 6, 5, 1]~ is ~(6+5)-(4+2+1) = 4~.

Dr. Henri knows that some of the data might be outliers, so he asks you ~Q~ queries of the form l r k, asking you to compute the ~k~-interest of the subarray ~A_l, A_{l+1}, \dots, A_r~.

Can you write a program to help Dr. Henri?

Constraints

Subtask 1 [10%]

~1 \le N, Q \le 4\,000~
~1 \le A_i \le 10^9~

Subtask 2 [60%]

~1 \le N, Q \le 200\,000~
~1 \le A_i \le 200\,000~

Subtask 3 [30%]

~1 \le N, Q \le 200\,000~
~1 \le A_i \le 10^9~

Input Specification

The first line of input will contain two space-separated integers, ~N~ and ~Q~.
The second line of input will contain ~N~ space-separated integers, ~A_1, A_2, \dots, A_N~.
The next ~Q~ lines will each contain three space-separated integers, ~l_i~, ~r_i~, and ~k_i~.
It is guaranteed that ~1 \le l_i \le r_i \le N~ and ~1 \le k_i \le 10^9~.

Output Specification

~Q~ lines, where the ~i^\text{th}~ line is the answer to the ~i^\text{th}~ query.

Sample Input 1

3 6
5 10 15
1 2 1
1 3 16
2 2 10
2 2 11
1 3 6
1 1 9

Sample Output 1

15
-30
10
-10
20
-5

Sample Input 2

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

Sample Output 2

17
49
-9
13
-15
4
-30
5
21
18