P8930 "TERRA-OI R1" God, Unafraid of Death.

The battle has reached its most intense stage. You are exhausted, and your arms keep shaking because they can no longer bear the weight of the great sword in your hands. Most of the God Eater’s purple shell has fallen off; it seems that it will shatter all over the ground after a few more heavy strikes. The purple mist in the sky starts to fade, and space gradually twists as it is torn apart again and again. In front of you, the God Eater tears open a rift one last time and launches its final blow at you in the most primitive way. You tighten your grip on the great sword and prepare to face this final strike. Even though you know this is the God Devourer’s last stubborn struggle, you still dare not relax for even a moment. After the final blow, a bell rings in the distance, and the battle will finally come to an end......

Lizi is going to play a game on a sequence $a$ of length $n$. Each time, he will take out all numbers whose indices are in $[l,r]$ and whose values are in $[p,q]$. Each time, he may choose two equal values among them and perform a **cancellation** operation, deleting these two numbers from the sequence. If and only if a value that originally existed is eliminated, then for every value smaller than it, each occurrence must be deleted once (for example, if the sequence originally has three $2$'s, after deleting once there will only be two $2$'s left), and the game will stop immediately. Lizi will play this game more than once, and the interval chosen each time is different. Also, to make the game harder, Lizi will sometimes modify the value of a number in the sequence. Now Lizi wants the minimum value in the remaining sequence to be as large as possible. You need to output, for each game, this maximum possible minimum value. In particular, if the game cannot stop, or if there exists a strategy that can eliminate the entire sequence, output $-1$.

The first line contains two positive integers $n,m$ separated by spaces, as described above. The second line contains $n$ positive integers separated by spaces, representing the sequence $a$. Lines $3$ to $m+2$ describe operations, each in one of the following two forms: - $1$ $p$ $x$: add $x$ to $a_p$. - $2$ $l$ $r$ $p$ $q$: query the result of playing the game on the subsequence with indices in $[l,r]$ and values in $[p,q]$.

For each query of type $2$, output one line with one integer, the answer.

#### Sample Explanation #1. For the first query, the extracted sequence is $[1,1,4,5,1,4]$. We first cancel two $1$'s, then cancel two $4$'s. At this time, the $1$'s that are smaller than $4$ will be deleted once, and the whole sequence only has one $5$ left. For the second query, we look at the first $4$ numbers. Since $5$ is not in the value range $[1,4]$, the extracted sequence is $[1,1,4]$. After canceling two $1$'s, the game ends immediately, and the answer is $4$. The third modification adds $1$ to $a_1$. After the modification, the sequence becomes $[2,1,4,5,1,4]$. For the fourth query, the extracted sequence is $[2,1,4]$. All numbers appear only once, so no cancellation can be performed. The game cannot stop, so output $-1$. For the fifth query, the extracted sequence is $[1,4,5,1,4]$. We choose to cancel two $1$'s. Since there is no $1$ left in the sequence, the game ends, and the minimum value is $4$. You may also cancel two $4$'s, but then the answer would be $1$, which is smaller than $4$. ------------ #### Constraints. **This problem uses bundled testdata.** | Subtask | Score | $n,m\le$ | limit | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10^3$ | None | | $2$ | $20$ | $10^5$ | Guaranteed that there is no operation $1$ | | $3$ | $30$ | $10^5$ | Guaranteed that for every operation $2$, $p=1,q=n$ | | $4$ | $40$ | $10^5$ | None | For $100\%$ of the data, $1\le n,m\le10^5$, and at any time $\forall i,a_i\in[1,n]$. For each operation $1$, $1\le p\le n$, $-n+1\le x\le n-1$, and $-a_p