Maximum Sum

Source: SPOJ

Version: Phuoc Hung OJ Extended

You are given an array $A_1,A_2,\ldots,A_N$. Process two kinds of operations:

• U i x: assign $A_i=x$.
• Q x y: for $1\le x<y\le N$, find the maximum possible sum of two elements at distinct positions inside $[x,y]$.

Print the answer for every Q operation.

Input

The first line contains $N$.

The second line contains $A_1,A_2,\ldots,A_N$.

The third line contains $Q$, the number of operations.

Each of the next $Q$ lines is either U i x or Q x y.

Output

For every Q operation, print the required maximum sum on its own line.

Subtasks

• Subtask 1 — 20%: $2\le N,Q\le 50$, $0\le A_i,x\le 10^4$.
• Subtask 2 — 30%: $2\le N,Q\le 5000$, $0\le A_i,x\le 10^8$.
• Subtask 3 — 50%: $2\le N\le 10^5$, $1\le Q\le 10^5$, $0\le A_i,x\le 10^8$.

Examples

Input

5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5

Output

7
9
11
12

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.