#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e6 + 10;
long long int jt[4 * N + 5], lz[4 * N + 5];
void prop(long long int l, long long int h, long long int p) {
  if (l != h) {
    lz[2 * p + 1] += lz[p];
    lz[2 * p + 2] += lz[p];
  }
  jt[p] += lz[p];
  lz[p] = 0;
  return;
}
void update(long long int l, long long int h, long long int p, long long int ql,
            long long int qh, long long int v) {
  if (lz[p]) prop(l, h, p);
  if (l >= ql && h <= qh) {
    lz[p] += v;
    prop(l, h, p);
    return;
  }
  if (l > qh || h < ql) return;
  long long int m = (l + h) >> 1;
  update(l, m, 2 * p + 1, ql, qh, v);
  update(m + 1, h, 2 * p + 2, ql, qh, v);
  jt[p] = min(jt[2 * p + 1], jt[2 * p + 2]);
  return;
}
long long int query(long long int l, long long int h, long long int p) {
  long long int m = (l + h) >> 1;
  if (lz[p]) prop(l, h, p);
  if (jt[p] >= 0)
    return -1;
  else if (l == h)
    return l;
  if (lz[2 * p + 2]) prop(l, h, 2 * p + 2);
  if (lz[2 * p + 1]) prop(l, h, 2 * p + 1);
  if (jt[2 * p + 2] < 0) return query(m + 1, h, 2 * p + 2);
  return query(l, m, 2 * p + 1);
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  srand(time(NULL));
  long long int n, m;
  cin >> n >> m;
  memset(jt, 0, sizeof(jt));
  memset(lz, 0, sizeof(lz));
  vector<long long int> a(n), b(m);
  for (long long int i = 0; i < n; i++)
    cin >> a[i], update(1, N, 0, 1, a[i], -1);
  for (long long int i = 0; i < m; i++)
    cin >> b[i], update(1, N, 0, 1, b[i], 1);
  long long int q;
  cin >> q;
  while (q--) {
    long long int t, p, q;
    cin >> t >> p >> q;
    p--;
    if (t == 1) {
      update(1, N, 0, 1, a[p], 1);
      a[p] = q;
      update(1, N, 0, 1, a[p], -1);
    } else {
      update(1, N, 0, 1, b[p], -1);
      b[p] = q;
      update(1, N, 0, 1, b[p], 1);
    }
    cout << query(1, N, 0) << "\n";
  }
}
