문제

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

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

입력

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

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

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