Range Chmin Chmax Add Range Sum

Source: Library Checker

Version: Phuoc Hung OJ Extended

Problem Statement

Given an integer sequence $a_0,a_1,\ldots,a_{N-1}$, process $Q$ queries on half-open ranges $[l,r)$:

• 0 l r b: set $a_i\leftarrow\min(a_i,b)$ for every $l\le i<r$.
• 1 l r b: set $a_i\leftarrow\max(a_i,b)$ for every $l\le i<r$.
• 2 l r b: set $a_i\leftarrow a_i+b$ for every $l\le i<r$.
• 3 l r: print $\sum_{i=l}^{r-1}a_i$.

Input

The first line contains $N,Q$. The second line contains $a_0,\ldots,a_{N-1}$. Each of the next $Q$ lines is a query of type 0, 1, 2, or 3 as described.

Output

For every type-3 query, print the range sum on its own line.

Subtasks

• Subtask 1 (20%): N,Q≤30; all other conditions are unchanged.

• Subtask 2 (30%): N,Q≤3000; all other conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le N,Q\le2\cdot10^5$

• $0\le l<r\le N$

• throughout all operations, $|a_i|\le10^{12}$ always holds

Examples

Input

5 8
1 2 3 4 5
3 0 5
0 1 5 3
3 0 5
1 0 3 2
2 2 5 4
3 1 4
0 0 5 6
3 0 5

Output

15
12
16
22

Explanation

The first sum is 15. Chmin on [1,5) gives [1,2,3,3,3] with sum 12. After chmax and add, the array becomes [2,2,7,7,7].