#include <bits/stdc++.h>
using namespace std;
const int _ = 1e6 + 7, N = 1e6, INF = 0x3f3f3f3f;
int n, m, q, a[_], b[_], tong[_];
struct node {
  int l, r, mi, lazy;
} t[_ << 2];
void pushup(int rt) { t[rt].mi = min(t[rt << 1].mi, t[rt << 1 | 1].mi); }
void pushdown(int rt) {
  if (t[rt].lazy) {
    t[rt << 1].lazy += t[rt].lazy, t[rt << 1].mi += t[rt].lazy;
    t[rt << 1 | 1].lazy += t[rt].lazy, t[rt << 1 | 1].mi += t[rt].lazy;
    t[rt].lazy = 0;
  }
}
void build(int l, int r, int rt) {
  t[rt].l = l, t[rt].r = r, t[rt].mi = INF;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
}
void modify(int rt, int L, int R, int ad) {
  if (L > R) return;
  if (L <= t[rt].l && t[rt].r <= R) {
    t[rt].lazy += ad, t[rt].mi += ad;
    return;
  }
  pushdown(rt);
  int mid = (t[rt].l + t[rt].r) >> 1;
  if (L <= mid) modify(rt << 1, L, R, ad);
  if (R > mid) modify(rt << 1 | 1, L, R, ad);
  pushup(rt);
}
int query(int rt) {
  if (t[rt].l == t[rt].r) return t[rt].l;
  pushdown(rt);
  if (t[rt << 1 | 1].mi < 0)
    return query(rt << 1 | 1);
  else
    return query(rt << 1);
}
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]);
  build(1, N, 1);
  for (int i = 1; i <= n; ++i) {
    if (!tong[a[i]]) modify(1, a[i], a[i], -INF);
    tong[a[i]]++;
    modify(1, 1, a[i], -1);
  }
  for (int i = 1; i <= m; ++i) modify(1, 1, b[i], 1);
  scanf("%d", &q);
  while (q-- > 0) {
    int opt, id, val;
    scanf("%d%d%d", &opt, &id, &val);
    if (opt == 1) {
      tong[a[id]]--;
      if (!tong[a[id]]) modify(1, a[id], a[id], INF);
      modify(1, 1, a[id], 1);
      a[id] = val;
      modify(1, 1, a[id], -1);
      if (!tong[a[id]]) modify(1, a[id], a[id], -INF);
      tong[a[id]]++;
    } else {
      modify(1, 1, b[id], -1);
      b[id] = val;
      modify(1, 1, b[id], 1);
    }
    if (t[1].mi >= 0)
      puts("-1");
    else
      printf("%d\n", query(1));
  }
  return 0;
}
