#include <bits/stdc++.h>
using namespace std;
const int N = 1111111;
const int MOD = 1e9 + 7;
const int intINF = 1e9;
const long long llINF = 2e18;
const double pi = acos(-1);
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
long long readll() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
struct node {
  int s, tag;
} t[N << 2];
int a[333333], b[333333], c[1111111], n, m;
void predo() {}
void init() {
  n = read(), m = read();
  for (int i = (int)1; i <= (int)n; i++) a[i] = read();
  for (int i = (int)1; i <= (int)m; i++) b[i] = read();
}
void pushdown(int p) {
  if (t[p].tag != 0) {
    t[p << 1].s += t[p].tag;
    t[p << 1 | 1].s += t[p].tag;
    t[p << 1].tag += t[p].tag;
    t[p << 1 | 1].tag += t[p].tag;
    t[p].tag = 0;
  }
}
void pushup(int p) { t[p].s = min(t[p << 1].s, t[p << 1 | 1].s); }
void build(int l, int r, int p) {
  t[p].tag = 0;
  if (l == r) {
    t[p].s = intINF;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, p << 1);
  build(mid + 1, r, p << 1 | 1);
  pushup(p);
}
void update(int l, int r, int x, int y, int z, int p) {
  if (x <= l && r <= y) {
    t[p].s += z;
    t[p].tag += z;
    return;
  }
  pushdown(p);
  int mid = (l + r) >> 1;
  if (x <= mid) update(l, mid, x, y, z, p << 1);
  if (y > mid) update(mid + 1, r, x, y, z, p << 1 | 1);
  pushup(p);
}
int query(int l, int r, int p) {
  if (t[p].s >= 0) return -1;
  if (l == r) return l;
  pushdown(p);
  int mid = (l + r) >> 1;
  if (t[p << 1 | 1].s < 0) return query(mid + 1, r, p << 1 | 1);
  return query(l, mid, p << 1);
}
void solve() {
  build(1, 1e6, 1);
  for (int i = (int)1; i <= (int)n; i++) {
    c[a[i]]++;
    if (c[a[i]] == 1) update(1, 1e6, a[i], a[i], -intINF, 1);
    update(1, 1e6, 1, a[i], -1, 1);
  }
  for (int i = (int)1; i <= (int)m; i++) update(1, 1e6, 1, b[i], 1, 1);
  int q = read();
  while (q--) {
    int op = read(), x = read(), y = read();
    if (op == 1) {
      update(1, 1e6, 1, a[x], 1, 1);
      c[a[x]]--;
      if (c[a[x]] == 0) update(1, 1e6, a[x], a[x], intINF, 1);
      a[x] = y;
      c[a[x]]++;
      if (c[a[x]] == 1) update(1, 1e6, a[x], a[x], -intINF, 1);
      update(1, 1e6, 1, a[x], -1, 1);
    }
    if (op == 2) {
      update(1, 1e6, 1, b[x], -1, 1);
      b[x] = y;
      update(1, 1e6, 1, b[x], 1, 1);
    }
    int ans = query(1, 1e6, 1);
    printf("%d\n", ans);
  }
}
int main() {
  predo();
  int cas = 1;
  while (cas--) {
    init();
    solve();
  }
  return 0;
}
