구간 더하기와 최댓값

난이도: Platinum IV 출제자: rlatjwls7882 시간 제한: 1000 ms 메모리 제한: 512 MB

느리게 갱신되는 세그먼트 트리세그먼트 트리

길이가 $N$인 수열 $A$가 있다. $Q$개의 쿼리를 순서대로 처리하라.

쿼리는 다음 중 하나이다.

1 l r x: $A_l,A_{l+1},\ldots,A_r$에 $x$를 더한다. $(1 \leq l \leq r \leq N,\ -10^9 \leq x \leq 10^9)$
2 l r: $A_l,A_{l+1},\ldots,A_r$의 최댓값을 출력한다. $(1 \leq l \leq r \leq N)$

입력

첫 번째 줄에 수열의 길이 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 200\,000)$

두 번째 줄에 수열의 원소 $A_1,A_2,\ldots,A_N$이 주어진다. $(-10^9 \leq A_i \leq 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.

모든 쿼리를 처리하는 동안 각 원소의 절댓값은 $10^{18}$을 넘지 않는다.

2 l r 쿼리마다 구간의 최댓값을 한 줄에 하나씩 출력한다.