Cho dãy ~a~ độ dài ~n~ và ~q~ thông tin thuộc một trong ~3~ loại sau:

• ~1\ l\ r\ x~ ~(1 \le l \le r \le n,\ 1 \le x \le 10^8)~: các phần tử trong đoạn ~l\ r~ được tăng thêm ~x~.

• ~2\ i~: thông tin thứ ~i~ là thông tin sai (dữ liệu đảm bảo thông tin thứ ~i~ thuộc loại ~1~ hoặc loại ~2~ và thông tin thứ ~i~ đã xuất hiện trước đó).

• ~3\ l\ r~ ~(1 \le l \le r \le n)~: tính tổng các số trong đoạn ~l\ r~.

Với mỗi truy vấn thuộc loại ~3~, in ra tổng cần tìm, biết rằng những thông tin đang không bị thông tin loại ~2~ chỉ vào thì chắc chắn là thông tin đúng, và không có hai thông tin loại ~2~ nào giống hệt nhau.

Input

• Dòng đầu nhập ~2~ số ~n~ và ~q~ ~(1 \le n,\ q \le 10^5)~ ~-~ tương ứng là số phần tử của dãy ~a~ và số thông tin .

• Dòng thứ hai nhập ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^8)~- tương ứng là các phần tử của dãy ~a~

• Trong ~q~ dòng tiếp theo, mỗi dòng nhập một thông tin thuộc một trong ~3~ loại theo định dạng như đề bài.

Output

• Với mỗi truy vấn thuộc loại ~3~, in ra tổng cần tìm.

Subtask

• ~20\%~ số test khác có ~1 \le n, q \le 2000~.

• ~80\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input

5 6
0 0 0 0 0
1 1 2 1
3 1 3
2 1
3 1 3
2 3
3 1 3

Sample Output

2
0
2