문제

길이가 $N$인 수열 $a_1\, a_2\, \cdots \, a_N$이 주어질 때, 다음 쿼리를 처리하는 프로그램을 작성해 보자.

• 1 l r x: $l ≤ i ≤ r$인 $a_i$에 대해 $a_i = a_i + x$를 적용한다.
• 2 l r y: $l ≤ i ≤ r$인 $a_i$에 대해 $a_i = \max(a_i, y)$를 적용한다.
• 3 l r y: $l ≤ i ≤ r$인 $a_i$에 대해 $a_i = \min(a_i, y)$를 적용한다.
• 4 l r: $a_l + a_{l+1} + \cdots + a_r$를 출력한다.

입력

첫째 줄에 수열의 크기 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 ≤ N,Q ≤ 500\,000)$

둘째 줄에는 $a_1, a_2, \cdots ,a_N$이 주어진다. $(-10^9 ≤ a_i ≤ 10^9)$

셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 각 쿼리는 $1\ l\ r\ x$ 또는 $2\ l\ r\ y$, $3\ l\ r\ y$, $4\ l\ r$이다. $(1 ≤ l ≤ r ≤ N, -1\,000 ≤ x ≤ 1\,000, -10^9 ≤ y ≤ 10^9)$

4번 쿼리는 한 번 이상 주어진다.

출력

4번 쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5 9
10 20 30 40 50
4 1 5
1 1 3 5
2 2 4 27
3 3 5 35
4 1 5
1 1 4 -2
2 2 5 40
3 1 5 30
4 1 5

예제 출력 1

150
147
133