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 containing at least sword. 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`

.

#### Constraints

For all subtasks:

##### Subtask 1 [5%]

##### Subtask 2 [5%]

##### Subtask 3 [30%]

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

.

##### Subtask 4 [60%]

#### Sample Input

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

#### Sample Output

`7`

## Comments

Any reason why changing my c++ vectors into arrays passed?

If you want to pass a vector, you can try passing the reference instead of the value.

I suspect passing vectors by value is slow (specifically, I think it requires an copy).

It's never mentioned that for the

`Q`

operation, at least one sword must be destroyed (even if it is better to not destroy any swords)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.