Background

There are many problems online where, given a sequence, you need to support several operations: A, B, C, D. Then you see another problem: again a sequence with operations to support: D, C, B, A. Especially someone here, when making a mock exam, even made one like this. Honestly, there is not much technical content in that...

So I will also make one. My goal is to let everyone have a “library” to rely on when solving such problems in the future, nothing else.

Let’s call this problem Sequence Terminator.

Problem Description

Given a sequence of length $N$, each element is an integer (trivial). You need to support the following three operations:

1. Add $V$ to every number in the interval $[L,R]$.
2. Reverse the interval $[L,R]$, for example, 1 2 3 4 becomes 4 3 2 1.
3. Query the maximum value in the interval $[L,R]$.

Initially, all elements are $0$.

Input Format

The first line contains two integers $N，M$. $M$ is the number of operations.

The next $M$ lines each contain up to four integers, in order: $K，L，R，V$. $K$ indicates the operation type. If it is not the $1$st operation, then only two numbers follow $K$.

Output Format

For each operation of type $3$, output the correct answer.

4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4

2

Hint

$1\le N \le 50000$，$1\le M \le 100000$，$|V| \leq 1000$。

Translated by ChatGPT 5