Problem description

Zadanie polega na znalezieniu podciągu spójnego o maksymalnej sumie (PSOMS). Dla przypomnienia: podciąg spójny ciągu jest to dowolny jego spójny kawałek od pewnego elementu do pewnego innego (w szczególności pusty ciąg jest podciągiem spójnym dowolnego ciągu). Pojęć sumy i maksimum chyba nie trzeba tłumaczyć.

Aby nie było za łatwo, elementy ciągu będą się często zmieniać, odpytywać będziemy się tylko o PSOMSy kawałków ciągu i będzie dużo, dużo zapytań.

Napisz program, który: wczyta ciąg liczb, zapytania i operacje zmiany ciągu, odpowie na wszystkie zapytania i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu. W drugim wierszu wejścia znajduje się ciąg N liczb całkowitych T_i, pooddzielanych pojedynczymi odstępami. Są to kolejne wyrazy ciągu, dla którego należy wyznaczyć wartość PSOMSa.

W trzecim wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę operacji/zapytań dotyczących ciągu. W kolejnych Q wierszach znajdują się informacje o zapytaniach i operacjach do wykonania na ciągu, po jednej w wierszu – wiersze składają się z litery określającej typ instrukcji O_i, pojedynczego odstępu oraz dwóch liczb całkowitych A_i, B_i oddzielonych pojedynczych odstępem: jeżeli O_i jest równe C – wiersz określa zmianę elementu numer A_i ciągu na wartość B_i, jeśli O_i jest równe Q to wiersz określa zapytanie o wartość podciągu spójnego o maksymalnej sumie dla podciągu spójnego elementów od A_i-tego do B_i-tego włącznie.

Elementy ciągu numerujemy kolejnymi liczbami naturalnymi od 1 do N.

Wyjście

Twój program powinien wypisywać odpowiedzi na zapytania (wiersze wejścia, w których O_i jest równe Q) zgodnie z kolejnością ich występowania i według aktualnej wiedzy, na temat ciągu – odpowiedzią na każde pytanie jest liczba całkowita – wartość podciągu o maksymalnej sumie (dla podciągu spójnego od A_i-tego elementu do B_i-tego włącznie).

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ Q ≤ 1 000 000,  − 10⁹ ≤ T_i ≤ 10⁹.

We wszystkich operacjach: 1 ≤ A_i ≤ N,  − 10⁹ ≤ B_i ≤ 10⁹. We wszystkich zapytaniach: 1 ≤ A_i ≤ B_i ≤ N.

Przykład

7
2 -3 4 -2 5 -10 3
5
Q 1 7
Q 1 4
C 6 -2
Q 1 7
Q 4 7

7
4
8
6