Link bài gốc : http://vnoi.info/problems/show/QMAX2/

Đề bài :

Giống bài QMAX (http://vnoi.info/problems/show/QMAX/) .

Input

• n: số phần tử của dãy (n <= 50000).- m: số lượng biến đổi và câu hỏi (m <= 100000).

  +) biến đổi có dạng: 0 x y value

  +) câu hỏi có dạng : 1 x y.

Output

Ghi ra trả lời cho lần lượt từng câu hỏi.

Example

Input:
6 3
0 1 3 3
0 4 6 4
1 1 6

Output:
4

Solution :

Tham Khảo Tại : http://dataurbia.com/10AY

Code :

Tham Khảo Tại : http://dataurbia.com/104N