407010 - 动态序列

给定一个含有 n 个数的序列 a1, a2，…，an，需要支持两种操作： 1．Q l r k 表示查询下标在区间 [l, r]（1 ≤ l ≤ r ≤ n，1 ≤ k ≤ r – l + 1）中的第 k 小的数； 2．C x y 表示将 ax 改为 y（1 ≤ x ≤ n，0 ≤ y ≤ 10^9）。

第一行两个正整数 n, m（1 ≤ n, m ≤ 10^5），表示序列长度与操作个数。 第二行 n 个整数，表示 a1, a2，…，an（0 ≤ ai ≤ 10^9）。 接下来 m 行，每行表示一个操作，都为上述两种中的一个。

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