You are given an array $$A$$ of N integers. You are required to answer $$Q$$ queries of the following types:

$$1 L R$$: Choose any two indices $$i$$, $$j$$ such that \(L \le i \le j \le R\) and find the maximum possible value of function F(i, j)
$$2 X V$$: Update the value of the element at index $$X$$ with $$V$$ that is set $$A[X] = V$$.

Function F(i,j) is defined as follows:

$$F(i, j) = 0$$, if all the elements in the subarray $$A[i..j]$$ are not equal. Otherwise, $$F(i, j) = A[i] + max(0, A[i + 1] - 1) + max(0, A[i + 2] - 2) + .... + max(0, A[j] - j + i)$$

Note: Assume 1-based indexing.

Input format

The first line contains two space-separated integers $$N$$ and $$Q$$ denoting the number of elements in array $$A$$ and the number of queries respectively.
The second line contains $$N$$ space-separated integers denoting the elements of array $$A$$.
Next $$Q$$ lines contain three space-separated integers denoting the queries.

Output format

For every query of type 1 in space-separated format, print the maximum possible value of function $$F$$.

Constraints

\(1 \le N, Q \le 3 \times 10^5 \\ 1 \le A[i], V \le 10^6 \\ 1 \le L \le R \le N \\ 1 \le X \le N \\\)