Segment Tree with Lazy Tag 1

Problem Description

You are given $n$ numbers $a_1, a_2, a_3, \dots, a_n$.

You must support $q$ operations:

1. 1 l r d: add $d$ to every $a_i$ with $l \le i \le r$.
2. 2 l r: query $\max_{i=l}^{r} a_i$.

Input Format

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The following $q$ lines each describe an operation of the form 1 l r d or 2 l r, with $1 \le l \le r \le n$ and $1 \le d \le 10^9$.

Output Format

For each query, output one line containing the answer.

Sample Input

5 5
1 2 3 4 5
2 4 5
1 1 5 1
2 1 4
1 2 3 10
2 2 4

Sample Output

5
5
14

Constraints

$1 \le n, q \le 2 \times 10^5$, $1 \le a_i, d \le 10^9$, $1 \le l \le r \le n$.