Cập nhật và Tính tổng trên Đoạn

Cho một mảng gồm $n$ phần tử. Bạn cần xử lý $q$ truy vấn thuộc ba loại:

1. Tăng mỗi giá trị trong đoạn $[a,b]$ thêm $x$.
2. Gán mỗi giá trị trong đoạn $[a,b]$ bằng $x$.
3. Tính tổng các giá trị trong đoạn $[a,b]$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$: kích thước mảng và số truy vấn.

Dòng thứ hai chứa $n$ số nguyên $t_1,t_2,\dots ,t_n$: các giá trị ban đầu của mảng.

• $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• 1 a b x — tăng mỗi giá trị trong đoạn $[a,b]$ thêm $x$

• 2 a b x — gán mỗi giá trị trong đoạn $[a,b]$ bằng $x$
• 3 a b — tính tổng các giá trị trong đoạn $[a,b]$

Dữ liệu ra

Với mỗi truy vấn loại 3, in ra tổng các giá trị trong đoạn tương ứng.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le t_i,x\le {10}^6$
• $1\le a\le b\le n$

Ví dụ