Cập nhật đoạn và tổng (Range Updates and Sums)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Duy trì mảng với ba thao tác: cộng một đoạn, gán một đoạn và tính tổng một đoạn.

Input

Dòng đầu chứa $n,q$, dòng tiếp theo chứa $n$ giá trị ban đầu. Mỗi truy vấn có một trong ba dạng:

• 1 a b x: cộng $x$ vào $[a,b]$.
• 2 a b x: gán mọi phần tử của $[a,b]$ thành $x$.
• 3 a b: tính tổng $[a,b]$.

Output

In đáp án cho mỗi truy vấn loại 3.

Subtask

• 20 điểm: $n,q\le50$.
• 30 điểm: $n,q\le5000$.
• 50 điểm: $1\le n,q\le2\cdot10^5$, $1\le t_i,x\le10^6$.

Ví dụ

Input

6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5

Output

7
11
15

Giải thích

Tổng $a_3+a_4+a_5$ ban đầu là $1+1+5=7$. Sau khi cộng 2 cho $[2,4]$ tổng này thành 11. Gán $[2,4]$ thành 5 khiến đoạn $[3,5]$ là 5 5 5, nên đáp án cuối là 15.