Can you answer these queries III

Source: SPOJ

Version: Phuoc Hung OJ Extended

Given an array $A_1,A_2,\ldots,A_N$, process two operations:

• 0 x y: assign $A_x=y$.
• 1 x y: print the maximum sum of a non-empty contiguous subarray inside $[x,y]$.

Input

The first line contains $N$.

The second line contains the array.

The third line contains $Q$.

The next $Q$ lines describe the operations.

Output

For every operation of type 1, print the answer on its own line.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$, $|A_i|,|y|\le 1000$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $|A_i|,|y|\le 10^4$.
• Subtask 3 — 50%: $1\le N,Q\le 50000$, $|A_i|,|y|\le 10^4$.

Examples

Input

4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Output

6
4
-3

Explanation

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