#include<bits/stdc++.h>
using namespace std;

#define N 503030 
int n,m;
int a[N],tree[N];
int ql[N],qr[N];

int lowbit(int x)
{
	return (x&(-x));
}

void add(int x,int t)
{
	for(int i = x; i <= n; i+=lowbit(i)) tree[i] += t;
}

int query(int x)
{
	int res = 0;
	for(int i = x; i >= 1; i-=lowbit(i)) res += tree[i];
	return res;
}

struct node{
	int l,r,t,k,op;
}o[N]; 
int ans[N],cnt,mn,mx,id[N];

void solve(int l,int r,int L,int R)
{
	if(l > r || L > R) return;
	//cout << L << R; 
	if(L == R)
	{
		for(int i = l; i <= r; i++) if(o[id[i]].op == 2) ans[id[i]] = L;
		return;
	}
	int mid = L + R >> 1;
	int ln = 0,rn = 0;
	for(int i = l; i <= r; i++)
	{
		if(o[id[i]].op == 0)
		{
			if(o[id[i]].k <= mid) ql[++ln] = id[i], add(o[id[i]].l,1);
			else qr[++rn] = id[i];
		}
		else if(o[i].op == 1)
		{
			if(o[id[i]].k <= mid) ql[++ln] = id[i], add(o[id[i]].l,-1);
			else qr[++rn] = id[i];
		}
		else
		{
			int tmp = query(o[id[i]].r) - query(o[id[i]].l - 1);
			if(tmp >= o[id[i]].k)
			{
				ql[++ln] = id[i];
			}
			else
			{
				qr[++rn] = id[i];
				o[id[i]].k -= tmp;
			}
		}
	}
	for(int i = 1; i <= ln; i++)
	{
		if(o[ql[i]].op == 0)
		{
			add(o[ql[i]].l,-1);
		}
		else if(o[ql[i]].op == 1)
		{
			add(o[ql[i]].l,1);
		}
	}
	for(int i = l; i < l + ln; i++) id[i] = ql[i - l + 1];
	for(int i = l + ln; i <= r; i++)id[i] = qr[i - ln - l + 1];
	if(ln)solve(l,l + ln - 1,L,mid);
	if(rn)solve(l + ln,r,mid + 1,R);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	mn = 1e9,mx = 0;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++)
	{
		o[++cnt] = (node){i,0,0,a[i],0};
		mx = max(mx,a[i]); mn = min(mn,a[i]);
	}
	for(int i = 1; i <= m; i++)
	{
		char c; cin >> c;
		if(c == 'Q')
		{
			int l,r,k; cin >> l >> r >> k;
			o[++cnt] = (node){l,r,cnt,k,2};
		}
		else
		{
			int l,k; cin >> l >> k;
			o[++cnt] = (node){l,0,cnt,a[l],1};
			o[++cnt] = (node){l,0,cnt,k,0};
			a[l] = k; // attention
			mn = min(mn,k);
			mx = max(mx,k);
		}
	}
	for(int i = 1; i <= cnt; i++) id[i] = i;
	
	solve(1,cnt,0,1e9+1);
	for(int i = 1; i <= cnt; i++)
	{
		if(o[i].op == 2)
		{
			cout << ans[i] << endl;
		}
	}
	return 0;
}