2488. 树套树-简单版

请你写出一种数据结构,来维护一个长度为 $n$ 的序列,其中需要提供以下操作:

  1. 1 pos x,将 $pos$ 位置的数修改为 $x$。
  2. 2 l r x,查询整数 $x$ 在区间 $[l,r]$ 内的前驱(前驱定义为小于 $x$,且最大的数)。

数列中的位置从左到右依次标号为 $1 \sim n$。

区间 $[l,r]$ 表示从位置 $l$ 到位置 $r$ 之间(包括两端点)的所有数字。

区间内排名为 $k$ 的值指区间内从小到大排在第 $k$ 位的数值。(位次从 $1$ 开始)

输入格式

第一行包含两个整数 $n,m$,表示数列长度以及操作次数。

第二行包含 $n$ 个整数,表示有序数列。

接下来 $m$ 行,每行包含一个操作指令,格式如题目所述。

输出格式

对于所有操作 $2$,每个操作输出一个查询结果,每个结果占一行。

数据范围

$1 \le n,m \le 5 \times 10^4$,
$1 \le l \le r \le n$,
$1 \le pos \le n$,
$0 \le x \le 10^8$,
有序数列中的数字始终满足在 $[0,10^8]$ 范围内,
数据保证所有操作一定合法,所有查询一定有解。

输入样例:

5 3
3 4 2 1 5
2 2 4 4
1 3 5
2 2 4 4

输出样例:

2
1