Cộng, Gán Và Lấy Tổng

Cho mảng $A$ gồm $N$ số nguyên. Bạn cần xử lý các thao tác trên đoạn đóng $[L,R]$:

1. cộng $X$ vào mọi phần tử;
2. gán mọi phần tử bằng $X$;
3. tính tổng các phần tử.

Các thao tác có hiệu lực theo đúng thứ tự xuất hiện. Đặc biệt, phép gán ghi đè mọi giá trị được tạo bởi các thao tác trước đó trên đoạn tương ứng.

Input

• Dòng đầu chứa hai số nguyên $N$ và $Q$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$.
• Mỗi dòng trong $Q$ dòng tiếp theo có một trong ba dạng:
• $1$ $L$ $R$ $X$: cộng $X$ vào đoạn $[L,R]$;
• $2$ $L$ $R$ $X$: gán đoạn $[L,R]$ bằng $X$;
• $3$ $L$ $R$: hỏi tổng đoạn $[L,R]$.

Output

• Với mỗi thao tác loại $3$, in một dòng chứa tổng cần tìm.

Constraints

• $1\le N,Q\le 2\cdot 10^5$.
• $1\le A_i,X\le 10^6$.
• $1\le L\le R\le N$.
• Dùng số nguyên $64$-bit cho tổng và giá trị trung gian.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N,Q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 7
1 2 3 4 5
3 1 5
1 2 4 3
3 2 5
2 3 5 2
3 1 5
1 1 3 4
3 2 4

15
23
12
17