#include <bits/stdc++.h>
using namespace std;
const int mxn = 300010;
int sd = 32323;
int ran() {
  return sd = (19260817ll * sd % 1000000007 + 323232323) ^ 998244353;
}
struct nd {
  int key, siz, num, mx, rnd, lazy;
  nd *ls, *rs;
} pool[2000010], *tp = pool, *rt, *Ta, *Tb;
void pushup(nd *i) {
  i->mx = i->num, i->siz = 1;
  if (i->ls) i->mx = max(i->mx, i->ls->mx), i->siz += i->ls->siz;
  if (i->rs) i->mx = max(i->mx, i->rs->mx), i->siz += i->rs->siz;
}
void change(nd *i, int x) {
  if (i) i->num += x, i->mx += x, i->lazy += x;
}
void pushdown(nd *i) {
  if (i->lazy) change(i->ls, i->lazy), change(i->rs, i->lazy), i->lazy = 0;
}
void spl(nd *i, int k, nd *&l, nd *&r) {
  if (!i) return (void)(l = r = 0);
  pushdown(i);
  if (i->key <= k)
    spl(i->rs, k, i->rs, r), pushup(l = i);
  else
    spl(i->ls, k, l, i->ls), pushup(r = i);
}
nd *mrg(nd *x, nd *y) {
  if (!x) return y;
  if (!y) return x;
  pushdown(x), pushdown(y);
  if (x->rnd < y->rnd)
    return x->rs = mrg(x->rs, y), pushup(x), x;
  else
    return y->ls = mrg(x, y->ls), pushup(y), y;
}
void ins(nd *&i, int k) {
  nd *x, *y, *t = ++tp;
  tp->key = k, tp->siz = 1, tp->rnd = ran();
  spl(i, k, x, y), i = mrg(mrg(x, t), y);
}
void del(nd *&i, int k) {
  nd *x, *y, *t;
  spl(i, k, x, y), spl(x, k - 1, x, t);
  pushdown(t);
  i = mrg(mrg(x, t->ls), mrg(t->rs, y));
}
nd *find(nd *i, int k) {
  if (i->ls && i->ls->siz >= k)
    return find(i->ls, k);
  else if (i->rs && i->siz - i->rs->siz < k)
    return find(i->rs, k - i->siz + i->rs->siz);
  else
    return i;
}
int qry(nd *i) {
  if (!i) return -1;
  pushdown(i);
  if (i->rs && i->rs->mx > 0)
    return qry(i->rs);
  else if (i->num > 0)
    return i->key;
  else
    return qry(i->ls);
}
int n, m, q, a[mxn], b[mxn];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ins(Ta, a[i]);
  for (int i = 1; i <= m; ++i) scanf("%d", &b[i]), ins(Tb, b[i]);
  for (int i = 1; i <= n; ++i) {
    int k = 0, v = find(Ta, i)->key;
    nd *x, *y;
    spl(Ta, v - 1, x, y);
    if (y) k += y->siz;
    Ta = mrg(x, y);
    spl(Tb, v - 1, x, y);
    if (y) k -= y->siz;
    Tb = mrg(x, y);
    y = ++tp;
    y->rnd = ran();
    y->key = v;
    y->siz = 1;
    y->num = y->mx = k;
    rt = mrg(rt, y);
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int typ, p, v;
    scanf("%d%d%d", &typ, &p, &v);
    if (typ == 1) {
      nd *x, *y, *t;
      int k = 0;
      spl(rt, a[p], x, y);
      change(x, -1);
      rt = mrg(x, y);
      spl(rt, v, x, y);
      change(x, 1);
      rt = mrg(x, y);
      del(Ta, a[p]);
      ins(Ta, v);
      spl(Ta, v - 1, x, y);
      if (y) k += y->siz;
      Ta = mrg(x, y);
      spl(Tb, v - 1, x, y);
      if (y) k -= y->siz;
      Tb = mrg(x, y);
      spl(rt, a[p], x, y);
      spl(x, a[p] - 1, x, t);
      pushdown(t);
      rt = mrg(mrg(x, t->ls), mrg(t->rs, y));
      t->key = v, t->ls = t->rs = 0, t->siz = 1;
      t->num = k, t->mx = k, t->lazy = 0;
      spl(rt, v, x, y);
      rt = mrg(mrg(x, t), y);
      a[p] = v;
    } else {
      nd *x, *y;
      spl(rt, b[p], x, y);
      change(x, 1);
      rt = mrg(x, y);
      spl(rt, v, x, y);
      change(x, -1);
      rt = mrg(x, y);
      del(Tb, b[p]);
      ins(Tb, v);
      b[p] = v;
    }
    printf("%d\n", qry(rt));
  }
  return 0;
}
