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!
Line : Two space separated integers, and .
Line : space separated integers, , the destructive power of Gilgamesh's original swords.
Lines : valid queries.
Print the answer to each query of the form
Q l r.
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]
8 2 1 2 3 4 5 6 7 8 S 1 2 Q 1 3