#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn = 6000000 + 5;

int A[maxn], arr[maxn];

int n, m, cnt;

struct Queries

{

	int c, l, r, k;

	Queries(int c = 0, int l = 0, int r = 0, int k = 0):c(c), l(l), r(r), k(k) {}

}asks[maxn];

struct Segment_Tree

{

	int lson[maxn * 10], rson[maxn * 10], root[maxn], temp[2][200], count[2], sumv[maxn * 10];

	int cnt_Tree;

	inline int lowbit(int t)

	{

		return t & (-t);

	}

	void insert(int l, int r, int pos, int delta, int &o)

	{

		if(!o) o = ++cnt_Tree;

		sumv[o] += delta;

		if(l == r) return;

		int mid = (l + r) >> 1;

		if(pos <= mid)

		    insert(l, mid, pos, delta, lson[o]);

		else

			insert(mid + 1, r, pos, delta, rson[o]);

	}

	inline void update(int pos, int val, int delta)

	{

		for(int i = pos;i <= n; i += lowbit(i))

			insert(1, n, val, delta, root[i]);

	}

	int query(int l, int r, int k)

	{

		if(l == r) return l;

		int sum = 0;

		for(int i = 1;i <= count[0]; ++i) sum += sumv[lson[temp[0][i]]];

		for(int i = 1;i <= count[1]; ++i) sum -= sumv[lson[temp[1][i]]];

		int mid = (l + r) >> 1;

		if(k <= sum) {

			for(int i = 1;i <= count[0]; ++i) temp[0][i] = lson[temp[0][i]];

			for(int i = 1;i <= count[1]; ++i) temp[1][i] = lson[temp[1][i]];

			return query(l, mid, k);

		}

		else

		{

			for(int i = 1;i <= count[0]; ++i) temp[0][i] = rson[temp[0][i]];

			for(int i = 1;i <= count[1]; ++i) temp[1][i] = rson[temp[1][i]];

			return query(mid + 1, r, k - sum);

		}

	}

	inline int Query(int l, int r, int k)

	{

		memset(temp, 0, sizeof(temp));

		count[0] = count[1] = 0;

		for(int i = r;i >= 1;i -= lowbit(i))

			temp[0][++count[0]] = root[i];

		for(int i = l - 1;i >= 1;i -= lowbit(i))

			temp[1][++count[1]] = root[i];

		return query(1, n, k);

	}

}T;

inline int get(int a)

{

    return lower_bound(A + 1, A + 1 + cnt, a) - A;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n; ++i)

	{

		scanf("%d",&arr[i]);

		A[i] = arr[i];

	}

	cnt = n;

	for(int i = 1;i <= m; ++i)

	{

		char opt[3];

		scanf("%s",opt);

		if(opt[0] == 'Q')

		{

			int a, b, c;

			scanf("%d%d%d",&a,&b,&c);

			asks[i] = Queries(0, a, b, c);

		}

		if(opt[0] == 'C')

		{

			int a, b;

			scanf("%d%d",&a,&b);

			asks[i] = Queries(1, a, a, b);

			A[++cnt] = b;

		}

	}

	n = cnt;

	sort(A + 1, A + 1 + cnt);

	for(int i = 1;i <= n; ++i)

	{

		int cur_num = get(arr[i]);

		T.update(i, cur_num, 1);

	}

	for(int i = 1;i <= m; ++i)

	{

		if(asks[i].c)

		{

			int origin_num = get(arr[asks[i].l]);

			T.update(asks[i].l, origin_num, -1);

			int cur_num = get(asks[i].k);

			T.update(asks[i].l, cur_num, 1);

			arr[asks[i].l] = asks[i].k;

		}

		else printf("%d\n", A[T.Query(asks[i].l, asks[i].r, asks[i].k)]);

	}

	return 0;

}