QMAX2 Giá trị lớn nhất ver2

Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0. Cho các phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị. Cho các câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]

Input

• Dòng đầu ghi 2 số nguyên dương n, m là số phần tử của dãy và số lượng biến đổi và câu hỏi (n <= 50000; m <= 100000).
• m dòng sau, mỗi dòng ghi 1 phép biến đổi hoặc câu hỏi.
• biến đổi có dạng: 0 u v k
• câu hỏi có dạng : 1 u v.

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

Input	Output
6 3 0 1 3 3 0 4 6 4 1 1 6	4