#include <bits/stdc++.h>
using namespace std;
const long long kmaxn = 2e6 + 5;
long long n, q, tmp;
pair<long long, long long> a[kmaxn];
unordered_map<long long, long long> mp;
set<pair<long long, long long>> st;
signed main() {
  cin.tie(0)->sync_with_stdio(false);
  long long T;
  for (cin >> T; T > 0; T--) {
    mp.clear(), st.clear();
    cin >> n >> q;
    fill(a + 1, a + n + 2, make_pair(-1e18, 0));
    for (long long i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i, mp[a[i].first]++;
    sort(a + 1, a + n + 1);
    for (long long i = 1, j; i <= n; i++) {
      for (j = i; j <= n && a[j].first <= a[j - 1].first + 1; j++);
      if (j <= n) st.emplace(a[j - 1].first + 1, a[j].first - 1);
      i = j;
    }
    st.emplace(a[n].first + 1, 1e18);
    sort(a + 1, a + n + 1, [&](pair<long long, long long> a, pair<long long, long long> b) { return a.second < b.second; });
    for (long long op, i, x; q > 0; q--) {
      cin >> op;
      if (op == 1) {
        cin >> i >> x, tmp = a[i].first;
        if (a[i].first != x) mp[a[i].first]--, a[i].first = x;
        if (mp[tmp] == 0) {
          pair<long long, long long> p = make_pair(tmp, tmp);
          auto r = st.lower_bound(p), l = st.upper_bound(p);
          if (r != st.end() && l != st.begin()) {
            l--;
            if (l->second == tmp - 1 && r->first == tmp + 1) st.erase(l), st.erase(r), st.emplace(l->first, r->second);
            else if (l->second == tmp - 1) st.erase(l), st.emplace(l->first, l->second + 1);
            else if (r->first == tmp + 1) st.erase(r), st.emplace(r->first - 1, r->second);
          }
          mp[x]++;
          if (mp[x] == 1) {
            pair<long long, long long> p = {x, 1e18};
            auto it = st.upper_bound(p);
            if (it != st.begin()) {
              it--, st.erase(it);
              if (it->first == x && it->second == x) {}
              else if (it->first == x) st.emplace(x + 1, it->second);
              else if (it->second == x) st.emplace(it->first, x - 1);
              else st.emplace(it->first, x - 1), st.emplace(x + 1, it->second);
            }
          }
        }
      } else {
        cin >> x;
        pair<long long, long long> p = {x, x};
        auto it = st.upper_bound(p);
        long long ans = 1e18;
        if (it == st.end()) ans = x;
        else {
          ans = it->first;
          if (it != st.begin()) { it--; if (it->second >= x) ans = x; }
        }
        cout << ans << '\n';
      }
    }
  }
  return 0;
}

已经被这个毒瘤题搞了 1h30m 了，eye 都瞎了。