题目描述

春风使时光微微萌动。时光在春意中飘散，俯视着努力仰望的我们。

在仰望什么呢？

是在仰望世界吗？世界的繁华聚焦于瞳孔之中，却像是散瞳了。看清了世界，却唯独模糊了自己。真爱的目光从这里逐渐变为过客的匆匆一瞥。

是在仰望神明吗？愚钝的人徘徊着，坠于嫉妒之谷，陷于拖沓之潭，铮铮地望着。聪慧的人踏出了脚步，却不知道自己挡住了多少人仰望的目光，堵住了多少人追赶的步伐。

是在仰望欲望吗？木偶的提线，似乎如何仰望都看不见操纵的手，只知道一根根线融入一个个数一行行字中，一次松动喜悦着心，一次收紧压迫了魂。只不过是虚无缥缈的，随着风无助地飘飘摇摇，一挥手，就在风中破碎，微弱的反光会逐渐消散，仿佛从未来过。

难道，是在仰望过去？

我伸出手，从房间的角落轻轻捧起一小缕时光，晶莹的光若隐若现。它在孤寂之处默默沉淀光彩，留存住岁月的足迹。在注视之下，它不停地扩展开来，张开一片片羽翼，直到占据了整个目光。它投映出一个个人。是你。是你们。是那个纯真的我。我轻轻张开指尖，一小滴时光滴落，这台建造在我手上的精妙机器渐渐塌陷，坠落，凝聚成我无法看见的一小片。

是岁月。我明白了。岁月的影子。

在太阳升起时，影子会默默出现。在意识沉睡时，影子为世人以刻下最美的碑痕。在太阳落下时，万物皆沉，唯有影子向上攀登。影子在黑暗中抚慰每一个迷路的人。

我想起了你。

不不要离去不要抛下我和回忆不要留下一个迷宫中徘徊的欲望与对比的提线木偶不要让我一个人在黑夜中缓缓回味不要留下我一个人追求 OI 之梦……

原来你也成为了我的影子，是吗？

当太阳的光辉普照大地时，只有影子能承担随之而来的黑暗。

我将手从角落收回，贴在胸前。

上帝知道，我愿意替你离去。

当我从朝圣之路坠入深渊，让我们一起刻下岁月的碑痕。

让我们一起仰望永恒的时光。

让我们一起变成影子吧。

给出一个长度为 $N$ 的序列 $a$, 进行 $Q$ 次操作：

操作 $1$ : 输入 $3$ 个正整数 $l,r,k$, 返回序列中第 $l$ 个数至第 $r$ 个数的区间中的第 $k$ 小值。

操作 $2$ : 输入 $2$ 个正整数 $x,k$, 在 $a$ 的第 $x$ 和第 $x+1$ 个位置之间插入一个值为 $k$ 的元素。

操作 $3$ : 输入 $1$ 个正整数 $x$, 将 $a$ 的第 $x$ 个元素删除。

输入格式

第 1 行输入两个整数 $N,Q$ .

第 2 行输入 $N$ 个整数，代表 $a_1,a_2,\dots, a_N$ .

接下来 $Q$ 行，每行输入 1 个整数 $\text{op},\text{op}\in \{1,2,3\}$. 。

• 当 $\text{op}=1$ 时，输入 $3$ 个整数 $l,r,k$, 代表操作 $1$；
• 当 $\text{op}=2$ 时，输入 $2$ 个整数 $x,k$, 代表操作 $2$；
• 当 $\text{op}=3$ 时，输入 $1$ 个整数 $x$, 代表操作 $3$。

输出格式

对于所有 $\text{op}_\text{i}=1$, 回答询问，一次询问占一行。

其余的操作无需进行任何输出。

样例组

输入#1

8 7
2 5 4 3 9 7 5 4
1 2 7 4
2 3 5
1 1 4 2
2 6 3
3 9
3 1
1 1 8 6

输出#1

5
4
5

提示说明

本题所有测试点分数一致。

对于 $10\%$ 的测试数据，保证 $1\leq N,Q\leq 500$.

对于另外 $20\%$ 的测试数据，保证对于所有 $1\leq i\leq Q$, $op_i=1$.

对于另外 $20\%$ 的测试数据，保证对于所有 $1\leq i<Q$, $op_i\in\{2,3\}$, $op_Q=1$.

对于所有 $100\%$ 的测试数据，$1\leq N\leq 10^5,1\leq Q\leq 2\times 10^5,0\leq a_i,k_j\leq 10^9,op\in \{1,2,3\},0\leq l_j\leq r_j\leq P,0\leq k_j\leq r_j-l_j+1,0\leq x_j\leq P$， 其中 $1\leq i\leq P,1\leq j\leq Q$.

数据范围中的 $P$ 表示进行当前操作时的的序列长度。即保证数据合理。

本题为避免非正解通过/获得部分分而进行了卡常，请尽可能优化常数。