Cho dãy \(a\) chứa \(N\) số nguyên. Cần phải thực hiện \(Q\) truy vấn thuộc \(3\) loại:

• \(2\) \(u\) \(v\): In ra tổng bình phương của các phần tử trong đoạn \([u, v]\) của mảng \(a\).
• \(1\) \(u\) \(v\) \(x\): Tăng tất cả các phần tử của mảng \(a\) trong đoạn \([u, v]\) lên \(x\) đơn vị \((|x| \leq 1000)\).
• \(0\) \(u\) \(v\) \(x\): Đặt \(x\) là giá trị cho tất cả các phần tử của mảng \(a\) trong đoạn \([u, v]\) \((|x| \leq 1000)\).

Input

• Dòng đầu chứa hai số \(N\) \((N \leq 100000)\) và \(Q\) \((Q \leq 100000)\), với \(N\) là độ dài của dãy \(a\) và \(Q\) là số lượng truy vấn.
• Dòng tiếp theo chứa \(N\) số \(a_{1}, a_{2}, \ldots, a_{N}\) \((|a_{i}| \leq 1000)\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn, mỗi truy vấn thuộc một trong \(3\) dạng:
  • \(2\) \(u\) \(v\)
  • \(1\) \(u\) \(v\) \(x\)
  • \(0\) \(u\) \(v\) \(x\)

Output

• In ra kết quả của các truy vấn.

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