暂无测试数据。

Description

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

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

Format

Input

第一行两个数 \(n,m\)，表示长度为 \(n\) 的有序序列和 \(m\) 个操作。

第二行有 \(n\) 个数，表示有序序列。

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

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

Output

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

Sample 1

Input

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

Output

2
4
3
4
9

Limitation

Data

\( 1 \leq n, m \leq 5 \times 10 ^ 4, -10 ^ 8 \leq k, x \leq 10 ^ 8 \)

Time and Space

4s, 256MB.

Source

loj #106

update by Shuchong