#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+5;
int n,m,rt[N],v[N<<5],ls[N<<5],rs[N<<5],siz[N<<5],a[N],cnt;

void pushup(int i)
{siz[i] = siz[ls[i]]+siz[rs[i]]+1;}

void split(int i,int k,int &x,int &y)
{
	if(!i) return (void)(x = y = 0);
	if(v[i] <= k) x = i,split(rs[i],k,rs[i],y),pushup(x);
	else y = i,split(ls[i],k,x,ls[i]),pushup(y);
}

mt19937 rnd(time(0));

int merge(int x,int y)
{
	if(!x || !y) return x|y;
	int rd = rnd()%(siz[x]+siz[y]);
	if(rd < siz[x]) {rs[x] = merge(rs[x],y);pushup(x);return x;}
	else {ls[y] = merge(x,ls[y]),pushup(y);return y;}
}

int New(int k)
{siz[++cnt] = 1;v[cnt] = k;return cnt;}

void ins(int i,int k)
{
	int x,y;split(rt[i],k,x,y);
	rt[i] = merge(merge(x,New(k)),y);
}

void add(int i,int a,int b)
{
	while(i <= n)
	{
		int x,y,z;split(rt[i],a,x,y);split(x,a-1,x,z);
		rt[i] = merge(merge(x,merge(ls[z],rs[z])),y);
		ins(i,b);
		i += i&-i;
	}
}

int rk(int i,int k)
{
	int x,y,ans;split(rt[i],k,x,y);
	ans = siz[x];rt[i] = merge(x,y);
	return ans;
}

int Q(int l,int r,int k)
{
	int sum = 0;
	while(r) sum += rk(r,k),r -= r&-r;
	while(l) sum -= rk(l,k),l -= l&-l;
	return sum;
}

int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
		cin >> a[i],add(i,0,a[i]);
	while(m--)
	{
		char ch;int l,r,k;cin >> ch >> l >> r;
		if(ch == 'Q')
		{
			cin >> k;
			int L = 0,R = 1e9;
			while(L < R)
			{
				int mid = (L+R)>>1;
				if(Q(l-1,r,mid) >= k) R = mid;
				else L = mid+1;
			}
			cout << L << '\n';
		}
		else add(l,a[l],r),a[l] = r;
	}
	return 0;
}