Tổng bình phương

Cho dãy số nguyên \(a\) gồm \(N\) phần tử. Nhiệm vụ của bạn là xử lý \(Q\) truy vấn trên dãy, mỗi truy vấn thuộc một trong ba loại sau:

• 2 u v --- In ra tổng các bình phương phần tử trong đoạn \([u, v]\).
• 1 u v x --- Cộng thêm \(x\) vào tất cả các phần tử trong đoạn \([u, v]\).
• 0 u v x --- Gán tất cả các phần tử trong đoạn \([u, v]\) bằng \(x\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) \((1 \leq N, Q \leq 10^5)\) --- số phần tử của dãy và số lượng truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) với \(|a_i| \leq 1000\).

• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn theo một trong ba định dạng sau:

• 2 u v \((1 \leq u \leq v \leq N)\).

• 1 u v x \((1 \leq u \leq v \leq N, -1000 \leq x \leq 1000)\).
• 0 u v x \((1 \leq u \leq v \leq N, -1000 \leq x \leq 1000)\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng các bình phương phần tử trong đoạn \([u, v]\) tại thời điểm đó.

Example

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

42
11
31

Scoring

• Subtask \(1\) (25% số điểm) : \(N, Q \leq 1000\).
• Subtask \(2\) (25% số điểm) : Không có thao tác loại \(1\).
• Subtask \(3\) (25% số điểm) : Không có thao tác loại \(0\).
• Subtask \(4\) (25% số điểm) : Không có ràng buộc gì thêm.