题目描述

给定一个含有 \(n\) 个数的序列 \(a_1,a_2 \dots a_n\)，需要支持两种操作：

• Q l r k 表示查询下标在区间 \([l,r]\) 中的第 \(k\) 小的数
  
• C x y 表示将 \(a_x\) 改为 \(y\)

格式

输入格式

第一行两个正整数 \(n,m\)，表示序列长度与操作个数。

第二行 \(n\) 个整数，表示 \(a_1,a_2 \dots a_n\)。

接下来 \(m\) 行，每行表示一个操作，都为上述两种中的一个。

输出格式

对于每一次询问，输出一行一个整数表示答案。

样例1

样例输入1

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

样例输出1

3
6

限制

对于 \(100\%\) 的数据，\(1\le n,m \le 10^5\)，\(1 \le l \le r \le n\)，\(1 \le k \le r-l+1\)，\(1\le x \le n\)，\(0 \le a_i,y \le 10^9\)。

请注意常数优化，但写法正常的整体二分和树套树都可以以大约 \(1000\text{ms}\) 每个点的时间通过。

来源

\(bzoj1901\)