题目描述

我需要治疗！我需要治疗！我需要治疗！我需要……

作为一名强大的牧师，小码哥需要为战场上的队友普照圣光，治疗他们。小码哥的圣光术十分强大，对仍存活的队友使用圣光术，小码哥可以增加他们的血量；对阵亡的队友使用圣光术，则可以复活这名队友，使其拥有一些血量，重新加入战斗。

然而，小码哥的圣光术需要看准时机使用，一是因为圣光术有冷却时间，且一次圣光术只能对一个队友生效；二是因为战场形势瞬息万变，对血量过高的队友使用没有太多作用，对血量过低的队友使用，则有可能还是无法使其血量高于他下一次收到攻击的伤害，然后阵亡，导致了治疗的浪费（毕竟小码哥可以选择直接复活他，不是么）。

所以，小码哥在治疗时，会选择当前活着的队友中，血量从小到大排名第$k_i$的队友，对其使用圣光术进行治疗。

战斗开始时，小码哥有$n$个队友，他们的初始血量依次为$h_i$，接下来战场上会发生$m$次变化。 变化一：1 x，表示有一个血量为$x$的队友阵亡了。 变化二：2 x，表示小码哥复活了一个队友，并将他的血量置为$x$。 变化三：3 x y，表示有一个血量为$x$的队友受伤，血量降至$y$。 变化四：4 k x，表示小码哥询问血量从小到大排名第$k_i$的队友，并使这个队友的血量增加$x$。

注意：所有变化的对象只有一个队友，即如果存在多名队友拥有同样的血量，也只会对其中一个队友产生变化。所有队友可以被认为没有血量上限，即接受的治疗量不会溢出，受到的治疗量将全部转化为血量的增加。

输入格式

第一行输入两个整数$n,m$； 第二行输入$n$个整数$h_i$，表示$n$名队友的初始血量； 接下来$m$行，每行一次变化，格式如题面所示。

输出格式

对于每次变化四，输出一行一个整数，询问对应的队友在接受治疗之前的血量。

样例输入 #1

5 5
10 20 50 40 30
4 3 10
1 10
2 20
4 1 10
4 1 10

样例输出 #1

30
20
20

说明/提示

有$1\leq n,m\leq 10^5,1\leq x,y\leq 10^9$。 对于变化一和变化三，保证血量为$x$的队友存在；对于变化四，保证当前活着的队友数量大于等于$k$。 保证每一时刻均不会出现血量大于$10^9$的队友。