Description

写一种数据结构（平 衡树）来维护一个有序数列，其中需要提供以下操作：

①查询$k$在区间 内的排名；

②查询区间内排名为$k$ 的值；

③修改某一位置上的数值；

④ 查询$k$在区间内的前驱（前驱指严格小于$x$ 且最大的数，若不存在，则 输出$-2147483647$）；

⑤查询$k$在区间内的后继（后继指严格大于$x$ 且 最小的数，若不存在，则输出$2147483647$）。

Format

Input

第$1$行包含两个整数$n 、m$ ，表示序列元素数量和操作数 量。

第$2$行包含$n$ 个数，表示有序序列。

接下来的$m$ 行，$opt$表示操作标 号，

若$opt=1$，则为操作①，之后有$3$个数$l 、r 、k$，表示查询$k$ 在$[l, r ]$区间的排名；

若$opt=2$，则为操作②，之后有$3$个数$l、r、k$ ，表 示查询$[l , r ]$区间排名为$k$的数；

若$opt=3$，则为操作③，之后有两 个数$pos、k$ ，表示将$pos$位置的数修改为$k$ ；

若$opt=4$，则为操作④， 之后有$3$个数$l、r、k$ ，表示查询$[l , r ]$区间$k$ 的前驱；

若$opt=5$，则 为操作⑤，之后有$3$个数$l、r、k$ ，表示查询$[l , r ]$区间$k$ 的后继。$n, m ≤5×10^4$ ，保证有序序列的所有值在任何时刻都满足$[0, 10^8]$。

Output

对操作①②④⑤各输出一行，表示查询结果。

Samples

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

2
4
3
4
9

来源

P3380/bzoj3196/Tyvj1730