SPOJ Brasil

Given a sequence A of N (N ≤ 100000) integers, you have to apply Q (Q ≤ 100000) operations:

Insert, delete, replace an element, find the maximum contiguous (non empty) sum in a given interval.

Input

The first line of the input contains an integer N.

The following line contains N integers, representing the starting sequence A1..AN, (|Ai| ≤ 10000).

The third line contains an integer Q. The next Q lines contains the operations in following form:

• I x y: insert element y at position x (between x - 1 and x).
• D x : delete the element at position x.
• R x y: replace element at position x with y.
• Q x y: print max{Ai + Ai+1 + .. + Aj | x ≤ i ≤ j ≤ y}.

All given positions are valid, and given values are between -10000 and +10000.

The sequence will never be empty.

Output

For each "Q" operation, print an integer (one per line) as described above.

Example

Input:
5
3 -4 3 -1 6
10
I 6 2
Q 3 5
R 5 -4
Q 3 5
D 2
Q 1 5
I 2 -10
Q 1 6
R 2 -1
Q 1 6

Output:
8
3
6
3
5