代码中inf的值设为1e9+2时，后50%的点RE；改为1e9 + 10后，后50%的点WA。

#include<bits/stdc++.h>
#define gc getchar
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10, inf = 1e9 + 10;

inline int read() {
	int x = 0; bool flag = 0; char ch = gc();
	for (;!isdigit(ch); ch = gc()) flag |= (ch == '-');
	for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return flag ? ~(x - 1) : x;
}

int n, m, tot;
int a[N], ans[N];

struct opt {
	int x, y, k;
	int type, id;
	
	// 对于询问, type = 1, x, y 表示区间左右边界, k 表示询问第 k 小
  	/* 对于修改, type = 0, x 表示修改位置, y 表示修改后的值,
  	k 表示当前操作是插入(1)还是擦除(-1), 更新树状数组时使用. */
  	// id 记录每个操作原先的编号, 因二分过程中操作顺序会被打散 
} q[N], q1[N], q2[N];

namespace BIT {
	int c[N];
	inline void add(int pos, int k) {
		#define lowbit(x) x&-x
		for (; pos <= n; pos += lowbit(pos)) c[pos] += k;
	}
	
	inline int query(int pos) {
		int res = 0;
		for (; pos; pos -= lowbit(pos)) res += c[pos];
		return res;
	}
}

inline void solve(int l, int r, int ql, int qr) {
	if (l > r || ql > qr) return ;
	if (l == r) {
		for (int i = ql; i <= qr; i ++)	
			if (q[i].type) ans[q[i].id] = l;
		return;
	}
	
	using namespace BIT;
	int mid = l + r >> 1, p1 = 0, p2 = 0;
	for (int i = ql; i <= qr; i ++)
		if (!q[i].type) {
			if (q[i].y > mid) q2[++p2] = q[i];
			else add(q[i].x, q[i].k), q1[++p1] = q[i];
		} else {
			int x = query(q[i].y) - query(q[i].x - 1);
			if (q[i].k <= x) q1[++p1] = q[i];
			else q[i].k -= x, q2[++p2] = q[i];
		}
	// roll back
	for (int i = 1; i <= p1; i ++)
		if (!q1[i].type) add(q1[i].x, -q1[i].k);
	for (int i = 1; i <= p1; i ++) q[ql + i - 1] = q1[i];
	for (int i = 1; i <= p2; i ++) q[ql + p1 + i - 1] = q2[i];
	solve(l, mid, ql, ql + p1 - 1);
	solve(mid + 1, r, ql + p1, qr);
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i ++)
		q[++tot] = {i, a[i] = read(), 1, 0};
	
	char op[2];
	for (int i = 1; i <= m; i ++) {
		scanf("%s", op);
		if (*op == 'C') {
			int x = read(), y = read();
			q[++tot] = {x, a[x], -1, 0, i}; a[x] = y;
			q[++tot] = {x, a[x], 1, 0, i};
		}
		else q[++tot] = {read(), read(), read(), 1, i};
	}
	
	memset(ans, -1, sizeof ans);
	solve(0, inf, 1, tot);
	for (int i = 1; i <= m; i ++)
		if (~ans[i]) printf("%d\n", ans[i]);
	return 0;
}