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

For example, the -interest of the array is .

Dr. Henri knows that some of the data might be outliers, so he asks you queries of the form `l r k`

, asking you to compute the -interest of the subarray .

Can you write a program to help Dr. Henri?

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [60%]

##### Subtask 3 [30%]

#### Input Specification

The first line of input will contain two space-separated integers, and .

The second line of input will contain space-separated integers, .

The next lines will each contain three space-separated integers, , , and .

It is guaranteed that and .

#### Output Specification

lines, where the line is the answer to the 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
```

## Comments

A similar problem which is a 12-pointer