#include <bits/stdc++.h>
#define space() putchar(' ')
#define endl() putchar('\n')
#define OFAST() ios::sync_with_stdio(false)
using namespace std;
const int N = 1e7 + 5;

int n, m, p;

int a[N], b[N], x[N], y[N], k[N];

char opt[N];

vector <int> tmp1, tmp2;

struct BIT {
	int d[N], rt[N];

	int tree[N], ls[N], rs[N], root;

#define mid ((l + r) >> 1)

	void update1(int &x, int l, int r, int p, int k) {
		if (!x) x = ++root;
		tree[x] += k;
		if (l == r) return ;
		if (p <= mid) return update1(ls[x], l, mid, p, k);
		return update1(rs[x], mid + 1, r, p, k);
	} // p 这个值 +k 次，正常做。

	int query1(int l, int r, int k) {
		if (l == r) return l;
		int sum = 0;
		for (auto v : tmp1) sum -= tree[ls[v]];
		for (auto v : tmp2) sum += tree[ls[v]];
		if (sum >= k) { // 正常计算
			for (auto &v : tmp1) v = ls[v];
			for (auto &v : tmp2) v = ls[v];
			return query1(l, mid, k);
		}
		for (auto &v : tmp1) v = rs[v];
		for (auto &v : tmp2) v = rs[v];
		return query1(mid + 1, r, k - sum);
	}

#undef mid

#define lowbit(x) (x & -x)

	void update(int x, int k) {
		int x1 = lower_bound(b + 1, b + 1 + p, a[x]) - b;
		for (int i = x1; i <= n; i += lowbit(i)) update1(rt[i], 1, p, x1, k);
		return ;
	} // 树状数组单点修改x这个值的个数。 log^2

	int query(int l, int r, int k) {
		tmp1.clear(), tmp2.clear();
		for (int i = l - 1; i; i -= lowbit(i)) tmp1.push_back(rt[i]);
		for (int i = r; i; i -= lowbit(i)) tmp2.push_back(rt[i]);
		return query1(1, p, k);
	} // 树状数组区间查询[l, r]的第k大，就是左边的（树状数组存）- 右边的（树状数组存），\
	其实这里的每个位子（题目中的a）都只记录了自己的值，然后求的前缀和。

#undef lowbit
} T;

signed main() {
//	OFAST();
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> b[++p], a[i] = b[p];
	for (int i = 1; i <= m; ++i) {
		cin >> opt[i];
		if (opt[i] == 'Q') cin >> x[i] >> y[i] >> k[i];
		else cin >> x[i] >> y[i], b[++p] = y[i];
	}

	sort(b + 1, b + 1 + p);
	p = unique(b + 1, b + 1 + p) - b - 1;

	for (int i = 1; i <= n; ++i) T.update(i, 1);

	for (int i = 1; i <= m; ++i) {
		if (opt[i] == 'Q') cout << b[T.query(x[i], y[i], k[i])] << "\n";
		else T.update(x[i], -1), a[x[i]] = y[i], T.update(x[i], 1);
	}
	return signed(0);
}
/*
5 1
3 2 1 4 7
Q 1 4 1
*/