#include<time.h>
#include<random>
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#define N 100001
using namespace std;

inline int read(){
	int ans = 0;
	char ch = getchar();
	while(!isdigit(ch)){
		ch = getchar();
	}
	while(isdigit(ch)){
		ans *= 10;
		ans += ch ^ 48;
		ch = getchar();
	}
	return ans;
}
inline void write(int n){
	if(n > 9) write(n / 10);
	putchar(48 ^ n % 10);
}

mt19937 rnd(time(0));

struct treap{
	struct Node{
		int val, cnt,siz;
		unsigned pri;
		Node *lc, *rc;
		Node(int val_){
			val = val_;
			cnt = siz = 1;
			pri = rnd();
			lc = rc = nullptr;
		}
		inline void update(){
			siz = cnt;
			if(lc != nullptr){
				siz += lc->siz;
			}
			if(rc != nullptr){
				siz += rc->siz;
			}
		}
	}*root;
	
	pair<Node*, Node*> split_by_val(Node *rt, int x){
		if(rt == nullptr){
			return make_pair(nullptr, nullptr);
		}
		if(rt->val <= x){
			pair<Node*, Node*> tmp = split_by_val(rt->rc, x);
			rt->rc = tmp.first;
			rt->update();
			return make_pair(rt, tmp.second);
		} else {
			pair<Node*, Node*> tmp = split_by_val(rt->lc, x);
			rt->lc = tmp.second;
			rt->update();
			return make_pair(tmp.first, rt);
		}
	}
	
	Node* merge(Node *l, Node *r){
		if(l == nullptr && r == nullptr){
			return nullptr;
		} else if(l == nullptr){
			return r;
		} else if(r == nullptr){
			return l;
		} else {
			if(l->pri > r->pri){
				r->lc = merge(l, r->lc);
				r->update();
				return r;
			} else {
				l->rc = merge(l->rc, r);
				l->update();
				return l;
			}
		}
	}
	
	void insert(int x){
		pair<Node*, Node*> tmp1 = split_by_val(root, x);
		pair<Node*, Node*> tmp2 = split_by_val(tmp1.first, x - 1);
		Node *tmp3;
		if(tmp2.second != nullptr){
			tmp2.second->cnt++;
			tmp2.second->update();
			tmp3 = merge(tmp2.first, tmp2.second);
		} else {
			Node *p = new Node(x);
			tmp3 = merge(tmp2.first, p);
		}
		root = merge(tmp3, tmp1.second);
	}
	
	void erase(int x){
		pair<Node*, Node*> tmp1 = split_by_val(root, x);
		pair<Node*, Node*> tmp2 = split_by_val(tmp1.first, x - 1);
		if(tmp2.second->cnt == 1){
			if(tmp1.first == tmp2.second){
				tmp1.first = nullptr;
			}
			delete tmp2.second;
			tmp2.second = nullptr;
		} else {
			tmp2.second->cnt--;
			tmp2.second->update();
			tmp2.first = merge(tmp2.first, tmp2.second);
		}
		root = merge(tmp2.first, tmp1.second);
	}
	
	int query_rk(Node *rt, int x){
		pair<Node*, Node*> tmp = split_by_val(rt, x - 1);
		int ans = 1;
		if(tmp.first != nullptr){
			ans += tmp.first->siz;
		}
		rt = merge(tmp.first, tmp.second);
		return ans;
	}
};

int n, m, a[N], lsh[N << 1], cnt;
struct opt{
	char type;
	int x, y, k;
}op[N];

struct segtree{
	#define lc rt << 1
	#define rc rt << 1 | 1
	
	treap node[N << 3];
	
	void insert(int rt, int l, int r, int pos, int k){
		node[rt].insert(k);
		if(l == r){
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) insert(lc, l, mid, pos, k);
		else insert(rc, mid + 1, r, pos, k);
	}
	
	void erase(int rt, int l, int r, int pos, int k){
		node[rt].erase(k);
		if(l == r){
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) erase(lc, l, mid, pos, k);
		else erase(rc, mid + 1, r, pos, k);
	}
	
	int query(int rt, int l, int r, int L, int R, int k){
		if(l == r){
			return l;
		}
		int mid = (l + r) >> 1;
		int tmp = node[lc].query_rk(node[lc].root, R + 1)
				- node[lc].query_rk(node[lc].root, L);
		if(tmp >= k) return query(lc, l, mid, L, R, k);
		else return query(rc, mid + 1, r, L, R, k - tmp);
	}
	
	#undef lc
	#undef rc
}tree;

int main(){
	n = read(), m = read();
	for(int i = 1; i <= n; ++i){
		a[i] = read();
		lsh[++cnt] = a[i];
	}
	
	for(int i = 1; i <= m; ++i){
		op[i].type = getchar();
		if(op[i].type == 'C'){
			op[i].x = read(), op[i].k = read();
			lsh[++cnt] = op[i].k;
		} else {
			op[i].x = read(), op[i].y = read(), op[i].k = read();
		}
	}
	
	sort(lsh + 1, lsh + cnt + 1);
	cnt = unique(lsh + 1, lsh + cnt + 1) - lsh;
	
	for(int i = 1; i <= n; ++i){
		int tmp = lower_bound(lsh + 1, lsh + cnt, a[i]) - lsh;
		tree.insert(1, 1, cnt, tmp, i);
	}
	
	for(int i = 1; i <= m; ++i){
		if(op[i].type == 'C'){
			int tmp = lower_bound(lsh + 1, lsh + cnt, a[op[i].x]) - lsh;
			tree.erase(1, 1, cnt, tmp, op[i].x);
			tmp = lower_bound(lsh + 1, lsh + cnt, op[i].k) - lsh;
			tree.insert(1, 1, cnt, tmp, op[i].x);
			a[op[i].x] = op[i].k;
		} else {
			write(lsh[tree.query(1, 1, cnt, op[i].x, op[i].y, op[i].k)]);
			putchar(10);
		}
	}
	return 0;
}