#include <bits/stdc++.h>
using namespace std;
seed_seq seq{
    (uint64_t)chrono::duration_cast<chrono::nanoseconds>(
        chrono::high_resolution_clock::now().time_since_epoch())
        .count(),
};
mt19937 rng(seq);
int n, m, a[300005], b[300005], q, first, p, t;
pair<int, int> sg[4000005];
void Upd(int nod, int l, int r, int p, int v) {
  if (l > p || r < p) return;
  if (l == r) {
    sg[nod].first += v;
    sg[nod].second += v;
    return;
  }
  int mid = (l + r) / 2;
  Upd(2 * nod, l, mid, p, v);
  Upd(2 * nod + 1, mid + 1, r, p, v);
  sg[nod].first = sg[2 * nod].first + sg[2 * nod + 1].first;
  sg[nod].second =
      max(sg[2 * nod + 1].second, sg[2 * nod + 1].first + sg[2 * nod].second);
}
int Qry(int nod, int l, int r, int v) {
  if (sg[nod].second < v) return -1;
  if (l == r) return l;
  int mid = (l + r) / 2;
  if (sg[2 * nod + 1].second >= v)
    return Qry(2 * nod + 1, mid + 1, r, v);
  else
    return Qry(2 * nod, l, mid, v - sg[2 * nod + 1].first);
}
int32_t main() {
  ios_base ::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    Upd(1, 1, 1e6, a[i], 1);
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    Upd(1, 1, 1e6, b[i], -1);
  }
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> t >> p >> first;
    if (t == 1) {
      Upd(1, 1, 1e6, a[p], -1);
      a[p] = first;
      Upd(1, 1, 1e6, a[p], 1);
    } else {
      Upd(1, 1, 1e6, b[p], 1);
      b[p] = first;
      Upd(1, 1, 1e6, b[p], -1);
    }
    cout << Qry(1, 1, 1e6, 1) << '\n';
  }
}
