Migrated from Lutece 2747 孤独的他，一个人数糖果

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

身怀足足 $n$ 罐糖果的菜猫在数糖果的时候感受到了寂寞，他认为仅仅去数第 $L$ 罐糖果到第 $R$ 罐糖果的总和太过无趣，于是他决定开始数第 $L$ 罐糖果到第 $R$ 罐糖果中第 $k$ 少的糖果数量。

简单的说，菜猫拥有 $n$ 罐糖果， 其中第 $i$ 罐糖果中初始有 $a_i$ 颗糖果。你需要帮助菜猫完成下列操作：

1. 查询下标在区间 $[L,R]$ 的所有糖果罐中糖果第 $k$ 小的数量。
2. 将第 $x$ 罐糖果中的数目改为 $y$

Input

第一行两个正整数 $n$, $m$, 表示糖果罐的数量与操作的数目。 第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个罐子里的初始糖果数量 $a_i$。 接下来 $m$ 行，开头是一个字符。

• 当这个字符为 $Q$ 的时候，代表操作 1，那么该行接下来还有三个正整数 $L$，$R$，$k$。
• 当这个字符为 $C$ 的时候，代表操作 2，该行接下来会有两个正整数 $x$，$y$。

Output

对于每一次询问的操作，请告诉菜猫答案。

Samples

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

3
6

Constraints

$1\le n,m \leq 10^5,0\le a_i, y \leq 32767$ $1\le x \leq n$ $1\le L \leq R \leq n$ $1\le k \leq R-L+1$

Resources

2022 UESTC ICPC Training for Data Structures