#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long a[1000110];
int L[1000110 << 2], R[1000110 << 2], lazy[1000110 << 2];
long long kmin[1000110 << 2], dx[1000110 << 2];
void build(int l, int r, int root) {
  if (l == r) {
    kmin[root] = a[l];
    L[root] = R[root] = l;
    lazy[root] = 0;
    dx[root] = 0;
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, (root << 1));
  build(mid + 1, r, ((root << 1) | 1));
  kmin[root] = min(kmin[(root << 1)], kmin[((root << 1) | 1)]);
  L[root] = l;
  R[root] = r;
  lazy[root] = 0;
  dx[root] = 0;
  return;
}
void update(int l, int r, long long p, int root) {
  if (l == L[root] && r == R[root]) {
    lazy[root] = 1;
    dx[root] += p;
    kmin[root] += p;
    return;
  }
  int Ll = L[root], Rr = R[root];
  int mid = (Ll + Rr) / 2;
  if (lazy[root]) {
    update(Ll, mid, dx[root], (root << 1));
    update(mid + 1, Rr, dx[root], ((root << 1) | 1));
    lazy[root] = 0;
    dx[root] = 0;
  }
  if (r <= mid) {
    update(l, r, p, (root << 1));
  } else if (l > mid) {
    update(l, r, p, ((root << 1) | 1));
  } else {
    update(l, mid, p, (root << 1));
    update(mid + 1, r, p, ((root << 1) | 1));
  }
  kmin[root] = min(kmin[(root << 1)], kmin[((root << 1) | 1)]);
}
int query(int l, int r, int root = 1) {
  int Ll = L[root], Rr = R[root];
  int mid = (Ll + Rr) / 2;
  if (l == Ll && r == Rr) {
    return kmin[root];
  }
  if (lazy[root]) {
    update(Ll, mid, dx[root], (root << 1));
    update(mid + 1, Rr, dx[root], ((root << 1) | 1));
    lazy[root] = 0;
    dx[root] = 0;
  }
  if (r <= mid) {
    return query(l, r, (root << 1));
  } else if (l > mid) {
    return query(l, r, ((root << 1) | 1));
  } else {
    return min(query(l, mid, (root << 1)),
               query(mid + 1, r, ((root << 1) | 1)));
  }
}
int dishes[1000110];
int pupils[1000110];
int solve() {
  int l = 1, r = 1e6, mid;
  if (query(l, r) >= 0) return -1;
  while (l < r) {
    mid = (l + r + 1) / 2;
    if (query(mid, r) < 0) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  return l;
}
void disp() {
  for (int i = 1; i <= 10; i++) {
    cout << query(i, i) << " ";
  }
  cout << endl;
}
void echo(int n, int m) {
  cout << "dish:";
  for (int i = 1; i <= n; i++) {
    cout << dishes[i] << " ";
  }
  cout << endl;
  cout << "pupils:";
  for (int i = 1; i <= m; i++) {
    cout << pupils[i] << " ";
  }
  cout << endl;
}
int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) == 2) {
    int x;
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; i++) {
      scanf("%d", &x);
      a[x]--;
      dishes[i] = x;
    }
    for (int i = 1; i <= m; i++) {
      scanf("%d", &x);
      a[x]++;
      pupils[i] = x;
    }
    for (int i = 1e6 + 1; i >= 0; i--) {
      a[i] += a[i + 1];
    }
    build(1, 1e6 + 5, 1);
    int q, id, index;
    scanf("%d", &q);
    int p1;
    for (int i = 0; i < q; i++) {
      scanf("%d%d%d", &id, &index, &x);
      p1 = id == 1 ? dishes[index] : pupils[index];
      if (id == 1)
        dishes[index] = x;
      else
        pupils[index] = x;
      if (x > p1) {
        update(p1 + 1, x, (id == 1 ? -1 : 1), 1);
      } else if (x < p1) {
        update(x + 1, p1, (id == 1 ? 1 : -1), 1);
      }
      printf("%d\n", solve());
    }
  }
  return 0;
}
