Background

Please do not abuse the judging system of this problem. If you abuse it, your account will be banned.

Problem Description

Given a sequence $a_1, \dots, a_n$, there are $m$ operations:

• Modify operation: given $l, r, x$, increase the values of $a_l, a_{l+1}, \dots, a_r$ by $x$.
• Query operation: given $l, r, x$, ask for the maximum, among all indices $i$ satisfying $l \le i \le r$ and $a_i < x$, of the historical maximum value of $a_i$ (i.e., the maximum among its initial value and its values after each modify operation).

Input Format

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

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

The next $m$ lines each contain four integers $o, l, r, x$, where $o = 1$ denotes a modify operation, and $o = 2$ denotes a query operation.

Output Format

For each query operation, output one line with the answer (in particular, if there is no index $i$ that satisfies the condition, output -inf).

5 10
-53 36 41 55 77
1 1 1 10
2 4 4 79
2 3 3 -28
1 1 5 -29
1 1 3 27
2 2 5 88
2 2 3 24
1 2 2 10
1 1 3 -9
1 2 5 -10

55
-inf
77
-inf

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $0\%$ of the testdata, $n, m \le 5000$.

For another $1/3\%$ of the testdata, the query operations guarantee $l = 1$ and $r = n$.

For another $1/3$ of the testdata, there are no modify operations.

For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $|a_i| \le 10^9$ (only the initially given sequence guarantees this limit), $1 \le l \le r \le n$, and $|x| \le 10^9$.

Translated by ChatGPT 5