## 我永远喜欢离线分治算法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
struct rec{
int t, x, y, z;
}a[maxn], lb[maxn], rb[maxn];
unordered_map<int,int> ump, rg;
set<int> st;
int n, m;
int seq[maxn];
int c[maxn], tot;
{
for(; x <= n; x += x & -x) c[x] += v;
}
{
int res = 0;
for(; x; x -= x & -x) res += c[x];
return res;
}
int ans[maxn];
void solve(int lv, int rv, int st, int ed)
{
if(st > ed) return ;
if(lv == rv)
{
for(int i = st; i <= ed; i++) ans[a[i].t] = lv;
return ;
}
int mid = (lv + rv) >> 1;
int lt = 0, rt = 0;
for(int i = st; i <= ed; i++)
{
if(a[i].t == -1)
{
if(ump[a[i].z] <= mid) add(a[i].x, -1), lb[++lt] = a[i];
else rb[++rt] = a[i];
}
else if(a[i].t == 0)
{
if(ump[a[i].z] <= mid) add(a[i].x, 1), lb[++lt] = a[i];
else rb[++rt] = a[i];
}
else
{
if(cnt >= a[i].z) lb[++lt] = a[i];
else a[i].z -= cnt, rb[++rt] = a[i];
}
}
for(int i = 1; i <= lt; i++) a[st + i - 1] = lb[i];
for(int i = 1; i <= rt; i++) a[st + lt + i - 1] = rb[i];
for(int i = st; i <= ed; i++)
if(a[i].t == 0 && ump[a[i].z] <= mid) add(a[i].x, -1);
else if(a[i].t == -1 && ump[a[i].z] <= mid) add(a[i].x, 1);
solve(lv, mid, st, lt + st - 1);
solve(mid + 1, rv, lt + st, ed);
}
int main()
{
int T; cin >> T;
while(T--)
{
int t = 0;
st.clear();
ump.clear();
rg.clear();
memset(c, 0, sizeof c);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%d", &seq[i]);
a[++t] = {0, i, i, seq[i]};
st.insert(seq[i]);
}
char op[5];
int qt = 0;
for(int i = 1; i <= m; i++)
{
scanf("%s", op);
if(*op == 'Q')
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
a[++t] = {++qt, l, r, k};
//st.insert(k);
}
else
{
int l, k;
scanf("%d%d", &l, &k);
a[++t] = {-1, l, l, seq[l]};
a[++t] = {0, l, l, k};
seq[l] = k;
st.insert(k);
}
}
tot = 0;
for(auto it = st.begin(); it != st.end(); it++) ump[*it] = ++tot, rg[tot] = *it;
//for(int i = 1; i <= t; i++) cout << a[i].x << " "; puts("");
solve(1, tot, 1, t);
for(int i = 1; i<= qt; i++) printf("%d\n", rg[ans[i]]);
}
}