Description

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

查询 $x$ 在区间内的排名； 查询区间内排名为 $k$ 的值； 修改某一位置上的数值； 查询 $x$ 在区间内的前驱（前驱定义为小于 $x$，且最大的数）； 查询 $x$ 在区间内的后继（后继定义为大于 $x$，且最小的数）。

Format

Input

第一行两个数 $n, m$，表示长度为 $n$ 的有序序列和 $m$ 个操作。 第二行有 $n$ 个数，表示有序序列 $a_i$。

下面有 $m$ 行，每行第一个数表示操作类型：

1. 之后有三个数 $l, r, x$ 表示查询 $x$ 在区间 $[l, r]$ 的排名；
2. 之后有三个数 $l, r, k$ 表示查询区间 $[l, r]$ 内排名为 $k$ 的数；
3. 之后有两个数 $\mathrm{pos}$, $y$ 表示将 $\mathrm{pos}$ 位置的数修改为 $y$；
4. 之后有三个数 $l, r, x$ 表示查询区间 $[l, r]$ 内 $x$ 的前驱；
5. 之后有三个数 $l, r, x$ 表示查询区间 $[l, r]$ 内 $x$ 的后继。

Output

对于操作 $1, 2, 4, 5$ 各输出一行，表示查询结果。

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

Limitation

$1 \leq n, m \leq 5 \times 10 ^ 4$

$0\le a_i,y\le 10^8$

$1\le l\le r\le n$

$1\le \mathrm{pos}\le n$

$1\le k\le r-l+1$

$-10^8\le x\le 10^8$

保证 $x$ 存在前驱和后继