Sau kỳ thi chọn đội tuyển tỉnh, White rơi vào một khoảng thời gian dài thất vọng. Cô không tìm thấy chút hy vọng nào trong kết quả của mình. Dù vậy, White vẫn tiếp tục đợt huấn luyện cuối cùng trước kỳ thi NOI. Bên cạnh việc luyện tập thường xuyên, cô cũng bắt đầu khám phá những chủ đề mà mình chưa từng có cơ hội học trong những ngày tháng OI — hy vọng rằng trước khi nói lời tạm biệt, sẽ không còn điều gì phải hối tiếc.

Gạt bỏ những suy nghĩ miên man, White bất chợt tập trung vào một bài toán trước mắt mình, một bài toán cấu trúc dữ liệu giản dị và nhàm chán —

White có một dãy gồm $n$ số nguyên $a_1, a_2, \dots, a_n$. Cô sẽ thực hiện $q$ thao tác trên dãy này. Mỗi thao tác thuộc một trong ba loại sau:

• 1 l r v — Cộng $v$ vào mỗi phần tử trong đoạn $[l, r]$.
• 2 l r v — Gán mỗi phần tử trong đoạn $[l, r]$ bằng $v$.
• 3 l r — Truy vấn giá trị $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ theo modulo $2^{64}$.

Nhiệm vụ của bạn là mô phỏng tất cả các thao tác và in ra kết quả của tất cả các truy vấn.

Dữ liệu

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n, q$ ($1 \le n, q \le 2 \times 10^5$), lần lượt biểu thị số lượng phần tử và số lượng thao tác.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), biểu thị các phần tử ban đầu.

Mỗi dòng trong $q$ dòng tiếp theo mô tả một thao tác theo một trong ba định dạng:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), biểu thị thao tác Cộng.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), biểu thị thao tác Gán.
• 3 l r ($1 \le l \le r \le n$), biểu thị thao tác Truy vấn.

Dữ liệu đảm bảo $0 \le a_i \le 10^9$ với mọi $1 \le i \le n$ trong suốt toàn bộ quá trình.

Kết quả

Với mỗi thao tác Truy vấn, in ra một số nguyên trên một dòng — kết quả của truy vấn theo modulo $2^{64}$.

Ví dụ

Dữ liệu

5 8
2 3 5 4 1
3 1 5
3 2 4
2 4 5 2
3 1 5
3 2 4
1 1 2 5
3 1 5
3 2 4

Kết quả

35
39
40
34
177
120

Dữ liệu

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10 1
3 1 5
3 2 9
3 8 10
1 2 5 10
3 1 5
3 2 9
3 8 10
1 5 9 -5
3 1 5
3 2 9
3 8 10
1 2 5 -10
3 1 5
3 2 9
3 8 10
1 5 9 5
3 1 5
3 2 9
3 8 10

Kết quả

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

Giải thích

Ở bộ test đầu tiên:

Dãy ban đầu là 2 3 5 4 1. Sau thao tác thứ ba, dãy trở thành 2 3 2 2 1, và sau thao tác thứ sáu, dãy trở thành 7 8 7 7 6.

Với truy vấn đầu tiên, đáp án là $\sum_{i=1}^5 (\min_{j=1}^i a_j) \times (\max_{j=1}^i a_j) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$.

Với truy vấn thứ hai, đáp án là $\sum_{i=2}^4 (\min_{j=2}^i a_j) \times (\max_{j=2}^i a_j) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$.