Arthuria is preparing to fight Gilgamesh for the Holy Grail! Unfortunately, Gilgamesh activates his Noble Phantasm, *Gate of Babylon*, and summons swords, and the has destructive power . Luckily for Arthuria, her Noble Phantasm, *Excalibur*, is capable of destroying any contiguous subsequence of Gilgamesh's swords. As such, Arthuria gives you queries of two possible forms:

`S i x`

: Gilgamesh swaps out the sword for one of destructive value .`Q l r`

: Arthuria simulates destroying the contiguous subsequence**with the maximum sum**in the range . Note that**she does not actually destroy these swords**.

As Arthuria's master, you wish to know the answer to all of the queries of the form `Q l r`

. Help win the Holy Grail!

#### Input Specification

Line : Two space separated integers, and .

Line : space separated integers, , the destructive power of Gilgamesh's **original** swords.

Lines : valid queries.

#### Output Specification

Print the answer to each query of the form `Q l r`

.

#### Subtasks

For all subtasks, , and .

##### Subtask 1 [5 points]

##### Subtaks 2 [5 points]

##### Subtask 3 [30 points]

All queries will be of the form `Q l r`

.

##### Subtask 4 [60 points]

#### Sample Input

```
8 2
1 2 3 4 5 6 7 8
S 1 2
Q 1 3
```

#### Sample Output

`7`

## Comments

Brute force passes. Please raise the limits if possible.

https://dmoj.ca/src/867148

Time limit for this question has been lowered, and AC submissions that were not intended (specifically brute force) have been rejudged.

insignificant's brute force solution still passes without a problem.

Another brute force solution just passed...

Is the empty sub-array an acceptable answer?

No

(well at least it doesn't pass the test cases...)

Thank you.