Cho một dãy gồm ~n~ phần tử có giá trị ban đầu bằng ~0~.

Cho ~m~ truy vấn có dạng:

• ~0~ ~x~ ~y~ ~k~: tăng mỗi phần tử từ vị trí ~x~ đến vị trí ~y~ lên ~k~ đơn vị.
• ~1~ ~x~ ~y~: cho biết giá trị lớn nhất của các phần tử có vị trí nằm trong đoạn [~x~, ~y~]

Input

• ~n~: số phần tử của dãy ~(n \leq 50000)~.

• ~m~: số lượng biến đổi và câu hỏi ~(m \le 10^5)~.

  • biến đổi có dạng: ~0~ ~x~ ~y~ ~k~ ~(1 \le k \le 10000)~
  • 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.

Sample Input

6 3
0 1 3 3
0 4 6 4
1 1 6

Sample Output

4