// author : black_trees

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

#ifndef ONLINE_JUDGE
  #include<cstdarg>
  #define meow(format, ...) \
    fprintf(stderr, format, ## __VA_ARGS__)
  // remember to open stream sync!
#else
  #define meow(format, ...) 1231
#endif

using namespace std;
using i64 = long long;

const int si = 1e5 + 10;

int n, m, len;
int a[si], id[si << 1];

int tot = 0;
int ls[si << 6], rs[si << 6];
int root[si << 6], dat[si << 6];

int cnt1, cnt2;
int tr1[si], tr2[si];

struct Query { char opt; int l, r, x; } q[si];

inline int lowbit(int x) { return x & -x; }
inline int getid(int val) { return lower_bound(id + 1, id + 1 + len, val) - id; }

int build(int l, int r) {
	int p = ++tot;
	if(l == r) return l;
	int mid = (l + r) >> 1;
	ls[p] = build(l, mid), rs[p] = build(mid + 1, r);
	return p;
}
int insert(int last, int l, int r, int val, int delta) {
	int p = ++tot;
	dat[p] = dat[last] + delta;
	if(l == r) return p;
	int mid = (l + r) >> 1;
	if(val <= mid) 
		ls[p] = insert(ls[last], l, mid, val, delta), rs[p] = rs[last];
	else
		rs[p] = insert(rs[last], mid + 1, r, val, delta), ls[p] = ls[last]; 
	return p;
}
int ask(int l, int r, int kth) {
	if(l == r) return l;
	int mid = (l + r) >> 1;
	int lcnt = 0;
	for(int i = 1; i <= cnt2; ++i) lcnt += dat[ls[tr2[i]]];
	for(int i = 1; i <= cnt1; ++i) lcnt -= dat[ls[tr1[i]]];

	if(kth <= lcnt) {
		for(int i = 1; i <= cnt1; ++i) tr1[i] = ls[tr1[i]];
		for(int i = 1; i <= cnt2; ++i) tr2[i] = ls[tr2[i]];
		return ask(l, mid, kth);
	}	
	else {
		for(int i = 1; i <= cnt1; ++i) tr1[i] = rs[tr1[i]];
		for(int i = 1; i <= cnt2; ++i) tr2[i] = rs[tr2[i]];
		return ask(mid + 1, r, kth - lcnt);
	}
}
// ask 挂了？？？？

void change(int x, int v) {
	int y = getid(a[x]), z = getid(v);
	while(x <= n) {
		root[x] = insert(root[x], 1, len, y, -1);
		root[x] = insert(root[x], 1, len, z, 1);
		x += lowbit(x);
	}
}
int query(int l, int r, int kth) {
	l --, cnt1 = cnt2 = 0;
	while(l) tr1[++cnt1] = root[l], l -= lowbit(l);
	while(r) tr2[++cnt2] = root[r], r -= lowbit(r);
	return ask(1, len, kth);
}


int main() {	

	// cin.tie(0) -> sync_with_stdio(false);
	// cin.exceptions(cin.failbit | cin.badbit);

	cin >> n >> m;
	int cnt = 0;
	for(int i = 1; i <= n; ++i)
		cin >> a[i], id[++cnt] = a[i];
	for(int i = 1; i <= m; ++i) {
		Query &p = q[i];
		cin >> p.opt;
		if(p.opt == 'C')
			cin >> p.l >> p.x, id[++cnt] = p.x;
		if(p.opt == 'Q')
			cin >> p.l >> p.r >> p.x;
	}

	sort(id + 1, id + 1 + cnt);
	len = unique(id + 1, id + 1 + cnt) - id - 1;

	root[0] = build(1, len);
	for(int i = 1; i <= n; ++i)
		root[i] = insert(root[i - 1], 1, len, getid(a[i]), 1);

	for(int i = 1; i <= m; ++i) {
		Query &p = q[i];
		if(p.opt == 'C') change(p.l, p.x), a[p.l] = p.x;
		if(p.opt == 'Q') cout << id[query(p.l, p.r, p.x)] << endl;
	}

	return 0;
}

难过，调了两三天了/....