Description

Given a sequence $a$ of length $n$, support the following three operations:

1. Given a range $[l, r]$, set every number in the range to $x$.
2. Given a range $[l, r]$, add $x$ to every number in the range.
3. Given a range $[l, r]$, query the maximum value in the range.

Input Format

The first line contains two integers, the length of the sequence $n$ and the number of operations $q$.
The second line contains $n$ integers, where the $i$-th integer is the $i$-th number $a_i$ in the sequence.
Then follow $q$ lines, each representing an operation. Each line starts with an integer $op$ indicating the type of operation.

• If $op = 1$, then there are three integers $l, r, x$, meaning set every number in the range $[l, r]$ to $x$.
• If $op = 2$, then there are three integers $l, r, x$, meaning add $x$ to every number in the range $[l, r]$.
• If $op = 3$, then there are two integers $l, r$, meaning query the maximum value in the range $[l, r]$.

Output Format

For each operation with $op = 3$, output one line with a single integer representing the answer.

6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6

7
6
-1

4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4

0

Hint

Constraints

• For $10\%$ of the testdata, $n = q = 1$.
• For $40\%$ of the testdata, $n, q \leq 10^3$.
• For $50\%$ of the testdata, $0 \leq a_i, x \leq 10^4$.
• For $60\%$ of the testdata, $op \neq 1$.
• For $90\%$ of the testdata, $n, q \leq 10^5$.
• For $100\%$ of the testdata, $1 \leq n, q \leq 10^6$, $1 \leq l, r \leq n$, $op \in \{1, 2, 3\}$, $|a_i|, |x| \leq 10^9$.

Please note the impact of large input on program efficiency.

Translated by ChatGPT 5