Cho dãy $A_1, A_2, \ldots, A_N$ có độ dài $N$. Hãy viết chương trình thực hiện các truy vấn sau:

• 0 l r x: Với mọi $l \le i \le r$, gán $A_i$ bằng $\max(A_i, x)$.
• 1 l r: In ra $\max\left(0, \max_{l \le u \le v \le r} \left(\sum_{i=u}^{v} A_i\right)\right)$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$, lần lượt là độ dài dãy và số lượng truy vấn.

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$, các phần tử ban đầu của dãy $A$.

$Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng trên.

Dữ liệu ra

Với mỗi truy vấn dạng 1 l r, in ra một dòng chứa kết quả.

Ví dụ

Dữ liệu vào 1

14 14
-3 2 1 -2 3 -4 3 -5 -1 -2 3 -5 1 5
1 3 9
0 1 14 -4
1 1 14
0 3 11 -1
1 2 8
0 3 10 -1
1 4 7
0 6 9 2
1 1 14
0 10 10 7
1 1 14
0 6 9 4
0 1 5 2
1 1 14

Dữ liệu ra 1

3
6
7
5
18
26
39