문제

길이가 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