Background

Subtask 0 uses the original testdata, and Subtask 1 uses hack testdata.

Problem Description

On a straight road from left to right, there are $n$ regions. Each region initially has a tree planted in it. The tree in region $i$ has height $h_i$. You need to process $q$ operations:

• 1 l r c: Increase the heights of all trees in regions $l$ to $r$ by $c$ units.
• 2 l r h: Fix a knife in the air at height $h$ and cut all trees in regions $l$ to $r$.
• 3 l r h: Plant a new tree of height $h$ in each region from $l$ to $r$.
• 4 l r: Query the height of the tallest tree in regions $l$ to $r$.

Note: In this problem, height is measured relative to some horizontal plane, so negative values may appear.

Input Format

The first line contains two integers $n, q$.

The second line contains $n$ integers $h_1, h_2, \cdots, h_n$.

The next $q$ lines each contain three or four integers: $op, l, r, c$, $op, l, r, h$, or $op, l, r$.

Output Format

Output several lines, each containing one integer, which is the answer to the corresponding query.

2 5
3 7
4 1 2
1 1 2 1
4 1 2
3 1 1 5
4 1 2

7
8
8

Hint

For $100\%$ of the data, $1 \leq n, q \leq 5 \times 10^5$, $1 \leq h_i \leq 10^9$, $1 \leq l \leq r \leq n$, $0 \leq |c| \leq 500$, $1 \leq h \leq 10^9$.

Translated by ChatGPT 5