#include <bits/stdc++.h>
using namespace std;
const int N = 303303, MAX = 1010101;
int n, m, q, a[N], b[N], cntA[MAX], cntB[MAX], t[MAX * 4], tmax[MAX * 4];
void pull(int v) {
  t[v] = t[v * 2] + t[(v * 2) + 1];
  tmax[v] = max(tmax[v * 2] + t[(v * 2) + 1], tmax[(v * 2) + 1]);
}
void build(int v, int L, int R) {
  if (L == R) {
    t[v] = cntA[L] - cntB[L];
    tmax[v] = t[v];
  } else {
    int M = (L + R) / 2;
    build(v * 2, L, M);
    build((v * 2) + 1, M + 1, R);
    pull(v);
  }
}
void updA(int v, int L, int R, int i, int d) {
  if (L == R) {
    cntA[L] += d;
    t[v] = cntA[L] - cntB[L];
    tmax[v] = t[v];
  } else {
    int M = (L + R) / 2;
    if (i <= M) {
      updA(v * 2, L, M, i, d);
    } else {
      updA((v * 2) + 1, M + 1, R, i, d);
    }
    pull(v);
  }
}
void updB(int v, int L, int R, int i, int d) {
  if (L == R) {
    cntB[L] += d;
    t[v] = cntA[L] - cntB[L];
    tmax[v] = t[v];
  } else {
    int M = (L + R) / 2;
    if (i <= M) {
      updB(v * 2, L, M, i, d);
    } else {
      updB((v * 2) + 1, M + 1, R, i, d);
    }
    pull(v);
  }
}
int get(int v, int L, int R, int need) {
  if (tmax[v] < need) {
    return -1;
  }
  if (L == R) {
    return L;
  }
  int M = (L + R) / 2;
  int ret = get((v * 2) + 1, M + 1, R, need);
  if (ret == -1) {
    ret = get(v * 2, L, M, need + t[(v * 2) + 1]);
  }
  return ret;
}
void changeA(int i, int x) {
  updA(1, 0, MAX - 1, a[i], -1);
  a[i] = x;
  updA(1, 0, MAX - 1, a[i], 1);
}
void changeB(int i, int x) {
  updB(1, 0, MAX - 1, b[i], -1);
  b[i] = x;
  updB(1, 0, MAX - 1, b[i], 1);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cntA[a[i]]++;
  }
  for (int j = 0; j < m; j++) {
    cin >> b[j];
    cntB[b[j]]++;
  }
  build(1, 0, MAX - 1);
  cin >> q;
  while (q--) {
    int s, i, x;
    cin >> s >> i >> x;
    i--;
    if (s == 1) {
      changeA(i, x);
    } else {
      changeB(i, x);
    }
    cout << get(1, 0, MAX - 1, 1) << '\n';
  }
  return 0;
}
