26460번 - 수열과 쿼리 41

길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$ 이 주어진다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 0 l r x: $l \le i \le r$ 에 대해 $A_i = max(A_i, x)$ 를 배정한다.
• 1 l r: $max(0, max_{l \le u \le v \le r} (\sum_{i = u}^{v} A_i))$ 를 출력한다.

첫 번째 줄에 수열의 길이 $N$ 과 쿼리의 수 $Q$ 가 주어진다.

두 번째 줄에 수열 $A$ 의 원소 $A_1, A_2, ..., A_N$ 이 주어진다.

이후 $Q$ 개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다.

모든 1 l r 형태의 쿼리에 대해 정답을 한 줄에 출력하라.

• $1 \leq N \leq 100\,000$
• $1 \leq Q \leq 200\,000$
• $-10^9 \le A_i, x \le 10^9$
• $1 \le l \le r \le N$