测试数据来自 system/1665

背景

JZP神牛看到了一道题，觉得太水了，于是交给yxyddd做，yxyddd也觉得太水了，把这题交给了yxy，yxy是个沙茶，根本没想法。所以这个只能交给你了。

描述

一个长度为n的序列，支持两种操作：
1.输出[A, B]区间第k小的数(从小到大排序后第k个)
2.修改第I个数为W

格式

输入格式

第一行两个整数N（1<=N<=50000),M(1<=M<=10000),表示有N个数，M个操作
第二行N个数AI
以下M行，每行一个操作
Q i j k（查询[I,J]中第k小的数）或 C i W(把第I个数改成W）

输出格式

对于每个查询操作，输出每个查询结果

样例1

样例输入1

5 3
1 2 3 4 5
Q 1 4 2
C 2 5
Q 1 4 2

样例输出1

2
3

限制

1s

提示

经典题目