#include <iostream>
#include <algorithm>
#define N 100005
using namespace std;
int n, m;
struct data
{
	int num;
	int id;
};
data a[N];
int b[N << 1];
int mp[N << 1];
int top;
bool cmp(data x, data y)
{
	return x.num < y.num;
}
struct que
{
	char op;
	int x, y, z;
};
que q[N];
struct node
{
	int l, r;
	int lc, rc;
	int data;
};
node tree[N << 8];
int size;
int root[N];
int lt[N], rt[N];
int topl, topr;
void pushup(int now)
{
	int lc = tree[now].lc;
	int rc = tree[now].rc;
	tree[now].data = tree[lc].data + tree[rc].data;
}
int build(int now, int l, int r)
{
	tree[now].l = l;
	tree[now].r = r;
	if (l == r)
	{
		return now;
	}
	int mid = l + r >> 1;
	tree[now].lc = build(++size, l, mid);
	tree[now].rc = build(++size, mid + 1, r);
	return now;
}
int add(int now, int x, int k)
{
	int now_ = ++size;
	tree[now_] = tree[now];
	int nl = tree[now_].l;
	int nr = tree[now_].r;
	if (nl == nr)
	{
		tree[now_].data += k;
		return now_;
	}
	int mid = nl + nr >> 1;
	if (x <= mid)
	{
		tree[now_].lc = add(tree[now_].lc, x, k);
	}
	else
	{
		tree[now_].rc = add(tree[now_].rc, x, k);
	}
	pushup(now_);
	return now_;
}
void modify(int now, int x, int k)
{
	int nl = tree[now].l;
	int nr = tree[now].r;
	if (nl == nr)
	{
		tree[now].data += k;
		return;
	}
	int mid = nl + nr >> 1;
	if (x <= mid)
	{
		if (tree[tree[now].lc].data)
		{
			modify(tree[now].lc, x, k);
		}
		else
		{
			tree[now].lc = add(tree[now].lc, x, k);
		}
	}
	else
	{
		if (tree[tree[now].rc].data)
		{
			modify(tree[now].rc, x, k);
		}
		else
		{
			tree[now].rc = add(tree[now].rc, x, k);
		}
	}
	pushup(now);
}
int ask(int l, int r, int k)
{
	int nl = tree[rt[1]].l;
	int nr = tree[rt[1]].r;
	if (nl == nr)
	{
		return nl;
	}
	int kkk = 0;
	for (int i = 1; i <= topl; ++i)
	{
		kkk -= tree[tree[lt[i]].lc].data;
	}
	for (int i = 1; i <= topr; ++i)
	{
		kkk += tree[tree[rt[i]].lc].data;
	}
	if (k <= kkk)
	{
		for (int i = 1; i <= topl; ++i)
		{
			lt[i] = tree[lt[i]].lc;
		}
		for (int i = 1; i <= topr; ++i)
		{
			rt[i] = tree[rt[i]].lc;
		}
		return ask(l, r, k);
	}
	else
	{
		for (int i = 1; i <= topl; ++i)
		{
			lt[i] = tree[lt[i]].rc;
		}
		for (int i = 1; i <= topr; ++i)
		{
			rt[i] = tree[rt[i]].rc;
		}
		return ask(l, r, k - kkk);
	}
}
void change(int v, int x, int k)
{
	for (int i = v; i <= n; i += (i & -i))
	{
		if (!root[i])
		{
			root[i] = add(root[0], x, k);
		}
		else
		{
			modify(root[i], x, k);
		}
	}
}
int query(int l, int r, int k)
{
	topl = 0;
	topr = 0;
	for (int i = l - 1; i; i -= (i & -i))
	{
		lt[++topl] = root[i];
	}
	for (int i = r; i; i -= (i & -i))
	{
		rt[++topr] = root[i];
	}
	return ask(l, r, k);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i].num;
		a[i].id = i;
	}
	int cnt = n;
	for (int i = 1; i <= m; ++i)
	{
		cin >> q[i].op;
		if (q[i].op == 'C')
		{
			cin >> q[i].x >> q[i].y;
			a[++cnt].num = q[i].y;
			a[cnt].id = cnt;
		}
		else
		{
			cin >> q[i].x >> q[i].y >> q[i].z;
		}
	}
	sort(a + 1, a + cnt + 1, cmp);
	for (int i = 1; i <= cnt; ++i)
	{
		if (a[i].num == a[i - 1].num)
		{
			b[a[i].id] = top;
		}
		else
		{
			b[a[i].id] = ++top;
		}
		mp[top] = a[i].num;
	}
	root[0] = build(++size, 1, top);
	for (int i = 1; i <= n; ++i)
	{
		change(i, b[i], 1);
	}
	int idx = n;
	for (int i = 1; i <= m; ++i)
	{
		if (q[i].op == 'C')
		{
			change(q[i].x, b[q[i].x], -1);
			b[q[i].x] = q[i].y;
			change(q[i].x, b[++idx], 1);
		}
		else
		{
			cout << mp[query(q[i].x, q[i].y, q[i].z)] << endl;
		}
	}
	return 0;
}

求助