#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 2100000;
int type[MAXN], child[MAXN][2], size[MAXN], f[MAXN], data[MAXN];
int tot;
int a[400000], b[400000];
int ll, rr;
int l, r, k, num;
int ttt, n, m;
int root[400000];
char c;
inline int getint()
{
static int t;
static bool tt;
tt = false;
t = 0;
c = getchar();
while (c != '\n' && c != ' '){
if (c == '-'){
tt = true;
c = getchar();
continue;
}
t = t * 10 + c - '0';
c = getchar();
}
if (tt) t = -t;
return t;
}
inline void putint(int t)
{
static char ch[10], *P;
P = ch;
if (t < 0) {
putchar('-');
t = -t;
}
ch[0] = 0;
while (t > 0){
*(P++) = t % 10 + '0';
t /= 10;
}
do {
putchar(*(--P));
} while (P != ch);
putchar('\n');
}
void Rot(int v)
{
int x = type[v];
int p = f[v];
int y = type[p];
int tmp = f[p];
f[v] = tmp;
type[v] = y;
if (y != 2)
child[tmp][y] = v;
y = 1 - x;
tmp = child[v][y];
if (tmp != 0){
f[tmp] = p;
type[tmp] = x;
}
child[p][x] = tmp;
f[p] = v;
type[p] = y;
child[v][y] = p;
size[p] = size[child[p][0]] + size[child[p][1]] + 1;
size[v] = size[child[v][0]] + size[child[v][1]] + 1;
}
void splay(int & root, int v)
{
while (1){
int x = type[v];
if (x == 2)
break;
int p = f[v];
int y = type[p];
if (x == y)
Rot(p);
else
Rot(v);
if (y == 2)
break;
Rot(v);
}
root = v;
}
void ins(int & root, int num)
{
int t = root;
while (1){
++size[t];
if (!child[t][num > data[t]]){
++tot;
size[tot] = 1;
data[tot] = num;
type[tot] = num > data[t];
f[tot] = t;
child[t][num > data[t]] = tot;
child[tot][0] = child[tot][1] = 0;
break;
}
else
t = child[t][num > data[t]];
}
splay(root, tot);
}
int getmax(int root)
{
int t = root;
while (child[t][1] > 0 )
t = child[t][1];
splay(root, t);
return root;
}
void find(int & root, int num)
{
int t = root;
while (data[t] != num)
t = child[t][num > data[t]];
splay(root, t);
}
int join(int t1, int t2)
{
if (t1 == 0)
return t2;
else{
f[t1] = 0;
type[t1] = 2;
}
if (t2 == 0)
return t1;
int t = getmax(t1);
child[t][1] = t2;
f[t2] = t;
return t;
}
void del(int & root, int num)
{
find(root, num);
root = join(child[root][0], child[root][1]);
f[root] = 0;
type[root] = 2;
size[root] = size[child[root][0]] + size[child[root][1]] + 1;
}
void maketree(int v, int l, int r)
{
tot++;
root[v] = tot;
data[tot] = a[l];
size[tot] = 1;
type[tot] = 2;
child[tot][0] = child[tot][1] = 0;
if (l == r)
return;
for (int i = l + 1; i <= r; i++)
ins(root[v], a[i]);
maketree(v << 1, l, (l + r) >> 1);
maketree((v << 1) + 1, ((l + r) >> 1) + 1, r);
}
void change(int v, int l, int r, int p, int num)
{
ins(root[v], num);
del(root[v], a[p]);
if (l == r)
return;
if (p <= ((l + r) >> 1))
change(v << 1, l, (l + r) >> 1, p, num);
else
change((v << 1) + 1, ((l + r) >> 1) + 1, r, p, num);
}
int rank(int root, int num)
{
if (root == 0)
return 0;
if (num >= data[root])
return size[child[root][0]] + 1 + rank(child[root][1], num);
else
return rank(child[root][0], num);
}
int que(int v, int l, int r, int ll, int rr, int num)
{
int tt = 0;
if (ll > r || l > rr) return 0;
if (ll <= l && rr >= r)
return rank(root[v], num);
int m = (l + r) >> 1;
if (ll <= m)
tt += que(v << 1, l, m, ll, rr, num);
if (r >= (m + 1))
tt += que((v << 1) + 1, m + 1, r, ll, rr, num);
return tt;
}
int query(int l, int r, int k)
{
ll = 1;
rr = n;
while (ll <= rr){
if (que(1, 1, n, l, r, b[(ll + rr) >> 1]) < k )
ll = ((ll + rr) >> 1) + 1;
else
rr = ((ll + rr) >> 1) - 1;
}
return b[ll];
}
int main()
{
//scanf("%d" ,&ttt);
ttt = 1;
while (ttt--){
tot = 0;
n = getint(); m = getint();
for (int i = 1; i <= n; i++) a[i] = getint();
memcpy(b, a, sizeof(a));
sort(b + 1, b + n + 1);
//getchar();
maketree(1, 1, n);
for (int i = 1; i <= m; i++){
char c = 'Q';
//scanf("%c", &c);
switch (c){
case 'C':
scanf("%d%d", &k, &num);
change(1, 1, n, k, num);
a[k] = num;
//getchar();
break;
case 'Q':
l = getint(); r = getint(); k = getint();
putint(query(l, r, k));
//getchar();
break;
}
}
}
}