Lớp học có ~n~ học sinh. Ban đầu, cô Nga có một danh sách đo độ thông minh của đội dự tuyển đã được sắp xếp tăng dần và cô cho các học sinh ngồi trên một đường thẳng theo thứ tự đó.

Sau khi cô Nga rời khỏi phòng, đôi khi sẽ có một nhóm học sinh có chỗ ngồi liên tiếp rủ nhau chơi Caro hoặc chơi xếp hình ngay tại chỗ. Do vậy, thi thoảng sẽ có nhóm học sinh ngồi từ vị trí ~L~ đến vị trí ~R~ cùng tăng hoặc cùng giảm một lượng độ thông minh.

Tuy nhiên, thỉnh thoảng cô Nga sẽ quay lại phòng để kiểm tra. Nếu cô thấy độ thông minh của học sinh trong phòng không còn tăng dần, cô sẽ phát hiện ra đó là điều không đúng. Do vậy, ngay khi cô vào phòng, lớp sẽ bắt đầu ngồi học. Kết quả là độ thông minh của các bạn đều giữ nguyên hoặc tăng lên. Do thời gian có hạn nên từng bạn trong lớp sẽ học ít nhất để sao cho độ thông minh của các học sinh vẫn phải là tăng dần theo chỗ ngồi đã được xếp (các học sinh vẫn giữ nguyên vị trí chỗ ngồi của mình).

Yêu cầu: Xuyên suốt trong quá trình này, Linh ngồi quan sát và đặt ra các câu hỏi về tổng độ thông minh của một nhóm học sinh ở vị trí liên tiếp là bao nhiêu. Bạn hãy giúp Linh nhé.

Input

• Dòng đầu ghi hai số nguyên ~n~ và ~t~ tương ứng là số học sinh trong lớp và số subtask của test này ~(1 \le n \le 5 \times 10^5, 1 \le t \le 5)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ là độ thông minh của các học sinh ban đầu luôn đảm bảo là dãy không giảm, nghĩa là ~a_{i-1} \le a_i~ với mọi ~2 \le i \le n~ ~(-10^6 \le a_i \le 10^6)~.

• Dòng thứ ba ghi số nguyên ~q~ là số sự kiện xảy ra ~(1 \le q \le 5 \times 10^5)~.

• Dòng thứ ~j~ trong số ~q~ dòng tiếp theo chứa miêu tả một sự kiện theo một trong các dạng sau:

  • 1 L R x: độ thông minh của nhóm học sinh có chỗ ngồi từ vị trí ~L~ đến vị trí ~R~ tăng thêm ~x~ (~1 \le L \le R \le n~; ~L, R, x~ là số nguyên và ~|x| \le 10^6~).

  • 2: cô Nga quay lại phòng để kiểm tra. Lúc này, độ thông minh của lớp sẽ thay đổi như đã miêu tả trên.

  • 3 L R: Linh đặt ra câu hỏi tổng độ thông minh của các học sinh từ vị trí ~L~ đến vị trí ~R~ (~L, R~ là số nguyên và ~1 \le L \le R \le n~).

Output

Với mỗi sự kiện loại ~3~, in ra một số là tổng độ thông minh mà Linh đặt ra.

Scoring

Sample Input 1

7 1
-5 -3 -3 0 1 4 5
6
1 3 4 3
2
3 2 6
1 2 5 -6
2
3 1 6

Sample Output 1

7
-17

Notes

Sau mỗi sự kiện, độ thông minh của các học sinh thay đổi như sau:

• Sau sự kiện đầu tiên (1 3 4 3), độ thông minh các học sinh lần lượt là: ~\{-5, -3, 0, 3, 1, 4, 5\}~.

• Sau sự kiện thứ hai (2): Học sinh thứ ~5~ có độ thông minh tăng lên ít nhất sau khi học là ~2~ để thành dãy không giảm là ~\{-5, -3, 0, 3, 3, 4, 5\}~.

• Ở sự kiện thứ ba (3 2 6), tổng độ thông minh của các học sinh từ vị trí ~2~ đến vị trí ~6~ là ~7~.

• Sau sự kiện thứ tư (1 2 5 -6): ~\{-5, -9, -6, -3, -3, 4, 5\}~.

• Sau sự kiện thứ năm (2): Độ thông minh tăng lên ít nhất sau khi học của học sinh thứ ~2~ và học sinh thứ ~3~ lần lượt là ~4~ và ~1~ để thành dãy không giảm là ~\{-5, -5, -5, -3, -3, 4, 5\}~.

• Ở sự kiện thứ sáu (3 1 6), tổng độ thông minh của các học sinh từ vị trí ~1~ đến vị trí ~6~ là ~-17~.