Cổ phiếu lao dốc

Bạn được giao nhiệm vụ quản lý một tài khoản gồm n cổ phiếu, trong đó mỗi cổ phiếu có giá trị ban đầu là a_i. Các cổ phiếu sẽ trải qua q ngày giao dịch trên sàn, trong đó vào ngày thứ j, một trong ba sự kiện sau có thể xảy ra:

• Sự kiện 1: Toàn bộ cổ phiếu từ vị trí u đến v rớt giá xuống còn 0.
• Sự kiện 2: Chủ tài khoản cần biết số tiền thu được nếu bán các cổ phiếu từ vị trí u đến v.
• Sự kiện 3: Các cổ phiếu từ vị trí u đến v đều tăng giá trị thêm một lượng là d.

Đầu vào: Dòng đầu tiên chứa hai số n ($1 \le n \le 10^5$) và $q$ ($1 \le q \le 10^5$) — số lượng cổ phiếu và số ngày.

Dòng thứ hai chứa n số nguyên — a_i ($\forall i, 1 \le i \le n, 0 \le a_i \le 10^9$) là giá trị ban đầu của cổ phiếu thứ i.

Trong q dòng tiếp theo, dòng thứ j chứa thông tin về sự kiện ở ngày thứ j:

• Nếu dòng chứa 3 số, sự kiện này thuộc loại 1 hoặc 2. Số đầu tiên là loại sự kiện (1 hoặc 2). Số thứ hai là giá trị u. Số cuối cùng là giá trị v.
• Nếu dòng chứa 4 số, sự kiện này thuộc loại 3. Số đầu tiên là 3. Ba số tiếp theo lần lượt là u, v và d.

Điều kiện: $1 \le u, v \le n, u \le v, 0 \le d \le 10^6$.

Đầu ra: Với mỗi thao tác thuộc loại 2, in ra tổng giá trị của các cổ phiếu từ vị trí u đến v.

Giải thích: Ban đầu, dãy n cổ phiếu có các giá trị như sau: 1 2 3 4 5 6

Sau mỗi ngày, giá trị của các cổ phiếu thay đổi như sau:

• Ngày 1: Không có cổ phiếu nào đổi giá. In ra tổng giá trị từ 3 đến 5: 3 + 4 + 5 = 12.
• Ngày 2: Không có cổ phiếu nào đổi giá. In ra 1 + 2 + 3 + 4 + 5 + 6 = 21.
• Ngày 3: 1 2 4 5 5 6.
• Ngày 4: Không có cổ phiếu nào đổi giá. In ra 4 + 5 = 9.
• Ngày 5: 1 2 0 0 5 6.
• Ngày 6: Không có cổ phiếu nào đổi giá. In ra 0 + 0 = 0.

Ví dụ 1:

Đầu vào:

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

Đầu ra:

12
21
9
0