Paula likes to prepare stir fry. In order to make it as yummy as possible, she needs to chop a sequence of integers into segments of the **maximum** total value.

The *value* of a segment is the **difference of its maximum and minimum**. The value of a chopped sequence is the sum of the values of the segments.

For example if we chop the sequence into segments and , the total value is .

There will be updates of the form "add to the elements on indices ". After each update, answer the query "What is the maximum possible value of the chopped sequence?".

#### Input Specification

The first line contains integers and , the length of the sequence and the number of updates.

The second line contains integers , the sequence Paula needs to chop.

Each of the following lines contains integers , , and , describing an update.

#### Output Specification

Output lines, the maximum possible value of the sequence after each update.

#### Constraints

Subtask | Points | Constraints |
---|---|---|

1 | 15 | |

2 | 40 | |

3 | 55 | No additional constraints. |

#### Sample Input 1

```
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
```

#### Sample Output 1

```
2
2
0
```

#### Explanation for Sample Output 1

Possible optimal choppings after each update are respectively: , , and .

#### Sample Input 2

```
4 3
2 0 2 1
4 4 1
2 2 3
1 3 2
```

#### Sample Output 2

```
2
1
3
```

## Comments