Migrated from Lutece 2953 Segment Balance

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小Z在遥远的国度里发现了水平排列的 $n$ 条线段。每一条线段对应一个长度。小Z将这 $n$ 条线段在水平地面上排成了平行的形状，并给它们赋予了编号。

形象的来说，最终的形状类似一个柱状图，每一个柱子即代表一条线段，柱子的高度即为线段长度，从左到右的编号分别为 $1...n$。

你需要维护以下 $5$ 种操作：

1. 查询长度为 $k$ 的线段（不一定在这 $n$ 条线段中出现）在编号为 $[l,r]$ 的所有线段的排名。
2. 查询在所有编号为 $[l,r]$ 的线段中长度排名为 $k$ 的线段的长度。
3. 修改编号为 $pos$ 的线段的长度。
4. 查询长度为 $k$ 的线段（不一定在这 $n$ 条线段中出现）在所有编号为 $[l,r]$ 的线段中的前驱线段的长度。
5. 查询长度为 $k$ 的线段（不一定在这 $n$ 条线段中出现）在所有编号为 $[l,r]$ 的线段中的后继线段的长度。

注意，以上的“排名”均指将所有元素在待操作区间中比该元素小的元素的个数加一，”前驱“定义为严格小于 $k$ 且最大的数，”后继“定义为严格大于 $k$ 且最小的数。若前驱不存在则输出 $-2147483647$，若后继不存在，则输出 $2147483647$ 。

Input

第一行两个数 $n, m$，表示有 $n$ 条线段和 $m$ 个操作。 第二行有 $n$ 个数，表示线段的长度。

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

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

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

Constraints

$1 \leq n,m \leq 5 \times 10^4,1 \leq pos \leq n, 1 \leq l \leq r \leq n$ ，同时保证任意时刻所有线段长度以及对长度的查询 $l_i \in [0,10^8]$，对于第二个操作，保证 $1 \leq k \leq r-l+1$

Resources

2023 UESTC ICPC Training for Data Structures