给定一个含有 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 行，每行表示一个操作，都为上述两种中的一个。

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

【数据范围】

对于 10\% 的数据，1\le n,m \le 100；
对于 20\% 的数据，1\le n,m \le 1000；
对于 50\% 的数据，1\le n,m \le 10^4；
对于 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。