Prefix Sum Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Given an array of $N$ integers, process $Q$ queries:

• 1 k u: assign $A_k=u$.
• 2 a b: find the maximum prefix sum inside the range $[a,b]$. The empty prefix with sum $0$ is allowed.

Thus a type 2 query asks for:

$$\max\left(0, A_a, A_a+A_{a+1},\ldots,A_a+\cdots+A_b\right).$$

Input

The first line contains $N,Q$.

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

The next $Q$ lines contain the queries.

Output

Print the answer for every type 2 query.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$, $|A_i|,|u|\le 10^4$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $|A_i|,|u|\le 10^9$.
• Subtask 3 — 50%: $1\le N,Q\le 2\cdot 10^5$, $|A_i|,|u|\le 10^9$.

Examples

Input

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

Output

5
2
0

Explanation

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