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

Update 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$, find the maximum historical value (the maximum value among the initial value and all values after each update operation) of $a_i$ for all $i$ such that $l \le i \le r$ and $a_i < x$.

Input

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 an update operation and $o=2$ denotes a query operation.

Output

For each query operation, output one line representing the answer (specifically, if no such $i$ exists, output -inf).

Examples

Input 1

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

Output 1

55
-inf
77
-inf

Subtasks

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

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

For another $1/3$ of the data, query operations guarantee $l=1, r=n$.

For another $1/3$ of the data, there are no update operations.

For $100\%$ of the data, $1 \le n, m \le 5 \times 10^5$, $|a_i| \le 10^9$ (only the initial sequence is guaranteed to satisfy this limit), $1 \le l \le r \le n$, $|x| \le 10^9$.