Truy vấn tổng tiền tố (Prefix Sum Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Cho mảng $A$ gồm $N$ số nguyên và $Q$ truy vấn:

• 1 k u: gán $A_k=u$.
• 2 a b: trong đoạn $[a,b]$, tìm tổng lớn nhất của một tiền tố của đoạn. Tiền tố rỗng có tổng $0$ được phép chọn.

Nói cách khác, với truy vấn loại 2, cần tính:

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

Input

Dòng đầu chứa $N,Q$.

Dòng thứ hai chứa $A_1,\ldots,A_N$.

$Q$ dòng tiếp theo là các truy vấn.

Output

In đáp án cho mỗi truy vấn loại 2.

Subtask

• 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$.

Ví dụ

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

Giải thích

Với đoạn $[2,6]$, các tổng tiền tố lần lượt là $2,1,4,5,0$, nên giá trị lớn nhất là $5$.