题目背景

战斗已经到了白热化阶段，你已经精疲力竭，手臂因承受不住手中巨剑重量不住地发抖，噬神者的紫色外壳已经脱落大半，似乎再承受几次重击就会碎落一地。天空中紫色的迷雾开始变得暗淡，空间由于被不断撕裂而逐渐扭曲。在你的身前，噬神者最后一次撕开裂缝，用最原始的方式向你发起最后一击。你握紧手中的巨剑，准备迎接这最后一击，即使你清楚这是神明吞噬者最后的倔强，可你依然不敢放松一分一毫。最后一击过后，远处响起了钟声，战斗终将落下帷幕......

题目描述

李子要在一个长度为 $n$ 的序列 $a$ 上玩游戏，他每次会把下标在 $[l,r]$ 范围内，且取值在 $[p,q]$ 范围内的所有数全部找出来，每次他可以选择其中两个相同的值，并进行抵消操作，将这两个数从数列中删除。当且仅当一个原本存在的值被消除掉后，所有值小于这个数的每个值全部要被删除一次（例如数列中原本有三个 $2$，进行一次删除后将会仅剩两个 $2$），并且这个游戏将会立即停止。

李子会不止一次的玩这个游戏，并且每次取的区间都不相同，而且，为了加大游戏难度，李子会时不时的修改序列中某个数的值。

现在李子想让剩下的数列中的最小值尽可能大，需要请你针对每次游戏，输出这个最大的最小值。特别地，如果这个游戏无法停止或者存在一种方案可以消除整个数列，输出 $-1$。

输入格式

第一行两个用空格分隔的正整数 $n,m$，含义见题目描述。

第二行 $n$ 个用空格分隔的正整数，表示对应 $a$ 序列。

第三行到第 $m+2$ 行，每行有以下两种情况：

• $1$ $p$ $x$ 表示给 $a_p$ 的值加上 $x$。
• $2$ $l$ $r$ $p$ $q$ 表示询问将下标属于 $[l,r]$，取值属于 $[p,q]$ 的数列取出进行游戏的结果。

输出格式

针对每个询问 $2$，输出一行一个整数表示答案。

6 5
1 1 4 5 1 4
2 1 6 1 5
2 1 4 1 4
1 1 1
2 1 4 1 4
2 2 6 1 5

5
4
-1
4

12 12
10 2 8 12 12 3 3 12 1 10 7 2
2 3 4 1 11
2 3 4 5 12
2 1 3 1 3
2 2 10 2 10
2 8 10 5 10
2 5 5 8 11
2 10 12 7 10
2 1 5 4 9
1 12 6
1 1 -6
2 5 8 5 12
2 5 8 2 12

-1
-1
-1
8
-1
-1
-1
-1
-1
12

提示

【样例解释 #1】

第一个询问对应的数列为 $[1,1,4,5,1,4]$，我们将两个 $1$ 先抵消，再抵消两个 $4$，此时比 $4$ 小的 $1$ 将会删除一次，整个序列只剩一个 $5$。

第二个询问针对前 $4$ 个数，且由于 $5$ 不属于 $[1,4]$ 值域范围，所以数列为 $[1,1,4]$，将两个 $1$ 抵消后游戏直接结束，答案为 $4$。

第三次修改将 $a_1$ 加 $1$，修改后数列为 $[2,1,4,5,1,4]$。

第四次询问对应的数列为 $[2,1,4]$，所有数据都只出现一次，没办法进行抵消操作，游戏无法停止所以输出 $-1$。

第五次询问的数列为 $[1,4,5,1,4]$，我们选择将两个 $1$ 抵消，由于数列中不再有 $1$，游戏结束，最小为 $4$。你也可以抵消两个 $4$，但这样答案为 $1$，比 $4$ 要小。

---

【数据范围】

本题采用捆绑测试。

Subtask	Score	$n,m\le$	limit
$1$	$10$	$10^3$	无
$2$	$20$	$10^5$	保证不存在操作 $1$
$3$	$30$		保证对于每个操作 $2$ ，$p=1,q=n$
$4$	$40$		无

对于 $100\%$ 的数据，$1\le n,m\le10^5$，对于任何时刻 $\forall i,a_i\in[1,n]$。

对于每个操作 $1$，$1\le p\le n$，$-n+1\le x\le n-1$ 并且 $-a_p<x\le n-a_p$。

对于每个询问 $2$，$1\le l \le r \le n$，$1\le p \le q \le n$。