Long Walk

One day Rupun the Rabit had a weird idea to go on a walk. She wants to go on a walk in one direction. Then she will walk in some other direction. Then She will walk some other direction. Then she will walk such a way that she returns to the exact place where she had started. But she cannot walk randomly. And she also wants to meet some conditions. But she is feeling lazy and so asked you to help her.

You will be given an array $A$. Rupun will give you $Q$ operations to perform, each of which will be a query or an update.

In each query, Rupun will give you a range of a subarray of $A$. You will have to choose 4 values from that array so that:

1. Rupun can use those values as length of walks.
2. The total length of walk is maximum possible.
3. Rupun should be able to walk so that no two path of walk should intersect except for the starting and ending point.

In each update, Rupun will give you 2 integers $x$ and $y$. You have to update the $x$-th value of $A$ with $y$, $A[x] = y$. (1-indexed)

You have to output the maximal total length of walk (Sum of the length of the four walks).

Input

The first line of input contains two integers, $N$ and $Q$ ($1 ≤ N,Q ≤ 5 \times 10^4$).

Next line will contain $N$ integers of the array $A$ ($1 ≤ A[i] ≤ 10^9$).

Each of the next $Q$ lines contain 3 integers, $t$, $x$ and $y$.

If $t$ is 0, then it is a query operation. You have to answer the query for the range $A[x], A[x+1], ..., A[y]$. If it is impossible to choose 4 values meeting the above conditions, then the answer is 0. ($1 ≤ x ≤ y ≤ N$)

If $t$ is 1, then it is an update operation. You have to make the update, $A[x] = y$. ($1 ≤ x ≤ N$ and $1 ≤ y ≤ 10^9$)

Output

For each query, print the answer in each line.

Samples

15 5
1 15 1 1 14 6 17 20 3 20 14 4 1 15 2 
0 1 7
1 7 9
0 7 14
0 11 15
1 8 18

52
69
35

15 5
12 18 19 19 10 12 14 11 16 2 16 1 18 13 3 
0 12 15
0 6 13
0 10 14
0 2 15
0 4 8

0
64
49
74
56