#include <bits/stdc++.h>
using namespace std;
const int MAX = 4000005, TOP = 1000000;
namespace segment_tree {
int pre[MAX], sum[MAX], lazy[MAX], maxx[MAX];
void build(int p, int l, int r) {
  if (l == r) {
    sum[p] = maxx[p] = pre[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  sum[p] = sum[p << 1] + sum[p << 1 | 1];
  maxx[p] = max(maxx[p << 1], maxx[p << 1 | 1]);
}
void add(int p, int l, int r, int del) {
  sum[p] += (r - l + 1) * del;
  lazy[p] += del;
  maxx[p] += del;
}
void pushdown(int p, int l, int r) {
  int mid = (l + r) >> 1;
  add(p << 1, l, mid, lazy[p]);
  add(p << 1 | 1, mid + 1, r, lazy[p]);
  lazy[p] = 0;
}
void modify(int p, int l, int r, int L, int R, int del) {
  if (L <= l && r <= R) return add(p, l, r, del);
  int mid = (l + r) >> 1;
  pushdown(p, l, r);
  if (L <= mid) modify(p << 1, l, mid, L, R, del);
  if (mid + 1 <= R) modify(p << 1 | 1, mid + 1, r, L, R, del);
  sum[p] = sum[p << 1] + sum[p << 1 | 1];
  maxx[p] = max(maxx[p << 1], maxx[p << 1 | 1]);
}
int qsum_sum(int p, int l, int r, int L, int R) {
  if (L <= l && r <= R) return sum[p];
  pushdown(p, l, r);
  int mid = (l + r) >> 1, ans = 0;
  if (L <= mid) ans += qsum_sum(p << 1, l, mid, L, R);
  if (mid + 1 <= R) ans += qsum_sum(p << 1 | 1, mid + 1, r, L, R);
  return ans;
}
int query(int p, int l, int r) {
  if (l == r) return l;
  pushdown(p, l, r);
  int mid = (l + r) >> 1;
  if (maxx[p << 1 | 1] >= 1)
    return query(p << 1 | 1, mid + 1, r);
  else if (maxx[p << 1] >= 1)
    return query(p << 1, l, mid);
  else
    return -1;
}
}  // namespace segment_tree
int n, m, q;
int a[TOP], b[TOP];
inline int read();
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), segment_tree::pre[a[i]]++;
  for (int i = 1; i <= m; ++i) b[i] = read(), segment_tree::pre[b[i]]--;
  for (int i = TOP; i >= 1; --i)
    segment_tree::pre[i] = segment_tree::pre[i] + segment_tree::pre[i + 1];
  segment_tree::build(1, 1, TOP);
  q = read();
  for (int i = 1; i <= q; ++i) {
    int type, pos, x;
    type = read();
    pos = read();
    x = read();
    switch (type) {
      case 1:
        segment_tree::modify(1, 1, TOP, 1, a[pos], -1);
        segment_tree::modify(1, 1, TOP, 1, x, 1);
        a[pos] = x;
        printf("%d\n", segment_tree::query(1, 1, TOP));
        break;
      case 2:
        segment_tree::modify(1, 1, TOP, 1, b[pos], 1);
        segment_tree::modify(1, 1, TOP, 1, x, -1);
        b[pos] = x;
        printf("%d\n", segment_tree::query(1, 1, TOP));
        break;
    }
  }
  return 0;
}
inline int read() {
  char tmp = getchar();
  int sum = 0;
  bool flag = false;
  while (tmp < '0' || tmp > '9') {
    if (tmp == '-') flag = true;
    tmp = getchar();
  }
  while (tmp >= '0' && tmp <= '9') {
    sum = (sum << 1) + (sum << 3) + tmp - '0';
    tmp = getchar();
  }
  return flag ? -sum : sum;
}
