#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
inline void Max(T &a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
inline void Min(T &a, U b) {
  if (a > b) a = b;
}
inline void add(int &a, int b) {
  a += b;
  while (a >= 998244353) a -= 998244353;
}
inline int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int pow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = ans * (long long)a % 998244353;
    a = (long long)a * a % 998244353;
    b >>= 1;
  }
  return ans;
}
const int M = 1000001;
int t[M << 2], mi[M << 2];
void upd(int p, int l, int r, int first, int v) {
  if (l == r) {
    t[p] += v;
    mi[p] = t[p];
    return;
  }
  int m = (l + r) >> 1;
  if (first <= m)
    upd(p << 1, l, m, first, v);
  else
    upd(p << 1 | 1, m + 1, r, first, v);
  t[p] = t[p << 1] + t[p << 1 | 1];
  mi[p] = min(mi[p << 1 | 1], mi[p << 1] + t[p << 1 | 1]);
}
int query(int p, int l, int r, int s = 0) {
  if (mi[p] + s >= 0) return -1;
  if (l == r) return l;
  int m = (l + r) >> 1;
  if (mi[p << 1 | 1] + s < 0) return query(p << 1 | 1, m + 1, r, s);
  return query(p << 1, l, m, s + t[p << 1 | 1]);
}
int a[300005], b[300005];
int main() {
  int j, k, i, T, ca = 0, m = 0, K = 0, n;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]), upd(1, 1, M - 1, a[i], -1);
  for (int i = 0; i < m; i++) scanf("%d", &b[i]), upd(1, 1, M - 1, b[i], 1);
  scanf("%d", &K);
  while (K--) {
    scanf("%d%d%d", &k, &i, &j);
    i--;
    if (k == 1) {
      upd(1, 1, M - 1, a[i], 1);
      a[i] = j;
      upd(1, 1, M - 1, a[i], -1);
    } else {
      upd(1, 1, M - 1, b[i], -1);
      b[i] = j;
      upd(1, 1, M - 1, b[i], 1);
    }
    printf("%d\n", query(1, 1, M - 1));
  }
}
