#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], ans[N], sum[N], vis[N], b[N], c[N];
struct Query{
  int op, id, x, y, k;
};
struct Node{
  int p, x;
};
int lowbit(int x){
  return x & -x;
}
void modify(int x, int y){
  if(vis[x] + y < 0 || vis[x] + y > 1)return;
  vis[x] += y;
  for(; x <= n; x += lowbit(x))sum[x] += y;
  return;
}
int query(int x){
  int ans = 0;
  for(; x; x -= lowbit(x))ans += sum[x];
  return ans;
}
void solve(int l, int r, vector<Node> a, vector<Query> q){
  if(l > r)return;
  if(l == r){
    for(Query i : q)if(i.op == 1)ans[i.id] = l;
    return;
  }
  int mid = (l + r) >> 1;
  vector<Node> a1, a2; vector<Query> q1, q2;
  for(Node i : a){
    if(i.x <= mid && i.x >= l)modify(i.p, 1), a1.push_back(i);
    else a2.push_back(i);
  }
  for(Query i : q){
    if(i.op == 0){
      modify(i.x, -1);
      if(i.y >= l && i.y <= mid)modify(i.x, 1), q1.push_back(i);
      else q2.push_back(i);
    }else{
      int x = query(i.y) - query(i.x - 1);
      if(x >= i.k)q1.push_back(i);
      else q2.push_back({i.op, i.id, i.x, i.y, i.k - x});
    }
  }
  for(Node i : a)modify(i.p, -1);
  for(Query i : q)if(i.op == 0)modify(i.x, -1);
  solve(l, mid, a1, q1), solve(mid + 1, r, a2, q2);
}
int main(){
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  vector<Node> v0;
  vector<int> c;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    c.push_back(a[i]);
  }
  char op;
  vector<Query> v2;
  for(int i = 1, l, r, k, x, y; i <= m; i++){
    cin >> op;
    if(op == 'Q')cin >> l >> r >> k, v2.push_back({1, i, l, r, k});
    else cin >> x >> y, v2.push_back({0, i, x, y, 0}), c.push_back(y);
    ans[i] = -1;
  }
  sort(c.begin(), c.end());
  map<int, int> mp, mp2;
  int cnt = 0;
  for(int i : c){
    if(!mp[i]){
      mp[i] = ++cnt;
      mp2[cnt] = i;
    }
  }
  for(int i = 1; i <= n; i++)v0.push_back({i, mp[a[i]]});
  for(Query &i : v2)if(i.op == 0)i.y = mp[i.y];
  solve(1, cnt, v0, v2);
  for(int i = 1; i <= m; i++){
    if(ans[i] != -1)cout << mp2[ans[i]] << '\n';
  }
  return 0;
}