#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = 4e6 + 5, _n = 1e6;
int n, m, a[N], b[N], lz[M], it[M], q;
void Down(int k) {
  int &tmp = lz[k];
  it[((k) << 1)] += tmp;
  lz[((k) << 1)] += tmp;
  it[((k) << 1) + 1] += tmp;
  lz[((k) << 1) + 1] += tmp;
  tmp = 0;
}
void update(int k, int l, int r, int i, int x) {
  if (i < l) return;
  if (r <= i) {
    it[k] += x;
    lz[k] += x;
  } else {
    Down(k);
    int m = (l + r) >> 1;
    update(((k) << 1), l, m, i, x);
    update(((k) << 1) + 1, m + 1, r, i, x);
    it[k] = max(it[((k) << 1)], it[((k) << 1) + 1]);
  }
}
int get(int k, int l, int r, int i) {
  if (r < i) return 0;
  if (i <= l) return it[k];
  Down(k);
  int m = (l + r) >> 1;
  return max(get(((k) << 1), l, m, i), get(((k) << 1) + 1, m + 1, r, i));
}
int bs() {
  if (get(1, 1, _n, 1) <= 0) return -1;
  int l = 1, r = _n, m;
  while (l < r) {
    m = (l + r + 1) >> 1;
    if (get(1, 1, _n, m) > 0)
      l = m;
    else
      r = m - 1;
  }
  return r;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 1; i <= m; ++i) scanf("%d", b + i);
  for (int i = 1; i <= n; ++i) update(1, 1, _n, a[i], +1);
  for (int i = 1; i <= m; ++i) update(1, 1, _n, b[i], -1);
  scanf("%d", &q);
  while (q--) {
    int t, i, x;
    scanf("%d%d%d", &t, &i, &x);
    if (t == 1) {
      update(1, 1, _n, a[i], -1);
      update(1, 1, _n, x, 1);
      a[i] = x;
    } else {
      update(1, 1, _n, b[i], 1);
      update(1, 1, _n, x, -1);
      b[i] = x;
    }
    printf("%d\n", bs());
  }
}
