Cho một dãy số gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ (với ~1 \le n \le 10^5, |a_i| \le 10^9~) và ~q~ truy vấn (~1 \le q \le 10^5~). Có hai loại truy vấn như sau:

• ~1~ ~l~ ~r~ ~x~: Cộng tất cả các phần tử trong đoạn ~[l, r]~ lên ~x~ đơn vị (với ~|x| \le 10^9~).
• ~2~ ~l~ ~r~ ~x~: Tính ~S = \sum_{i = l}^{r} |a_i - x|~ (với ~|x| \le 10^9~).

INPUT

Dòng đầu tiên nhập vào hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 10^5~)

Dòng tiếp theo nhập vào ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~)

~q~ dòng cuối cùng, mỗi dòng nhập vào một trong hai loại truy vấn ~1~ ~l~ ~r~ ~x~ hoặc ~2~ ~l~ ~r~ ~x~ với ý nghĩa như trên.

OUTPUT

In ra nhiều dòng, mỗi dòng là đáp số của mỗi truy vấn loại ~2~ ~l~ ~r~ ~x~.

SAMPLE INPUT

5 5
1 5 2 4 3
2 1 5 3
1 2 4 1
2 1 5 3
1 1 5 -2
2 3 5 1

SAMPLE OUTPUT

6 
7
2