Cho mảng \(A\) gồm \(N\) phần tử và \(Q\) truy vấn khác nhau, nhiệm vụ của bạn là thực hiện các truy vấn sau:

• 1 L R X: Thay thế tất cả các phần tử của mảng \(A\) trong đoạn \([L;R]\) bằng \(X\).
• 2 L R X: Cộng \(X\) vào \(A[L]\), \(2\times X\) vào \(A[L+1]\), \(3\times X\) vào \(A[L+2]\), ... , \((R-L+1)\times X\) vào \(A[R]\).
• 3 C X: Chèn \(X\) vào vị trí \(C\) của mảng \(A\).
• 4 L R: Tính tổng các phần tử trong đoạn \([L;R]\).

Input

• Dòng đầu tiên là hai số nguyên dương \(N, Q\) là số phần tử mảng \(A\) và số lượng truy vấn \((1\leq N, Q\leq 10^5)\).
• Dòng thứ hai gồm \(N\) số nguyên là các giá trị của mảng \(A\). Các phần tử của mảng không vượt quá \(10^5\).
• \(Q\) dòng tiếp theo, mỗi dòng là các truy vấn. Trong tất cả các truy vấn, \(1\leq X\leq 100\), \(1\leq L\leq R\leq\)Độ dài hiện tại của mảng và \(1\leq C\leq\)Độ dài hiện tại của mảng \(+1\).

Output

• Gồm nhiều dòng, mỗi dòng là kết quả của truy vấn loại \(4\).

Example

10 10
1 2 3 4 5 6 7 8 9 10
1 2 8 15
2 3 7 26
4 2 7
3 6 100
1 4 8 52
2 2 9 18
4 3 10
2 1 8 45
3 8 82
4 1 11 

480
955
2691