#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1e5;
int it[4 * N], lazy[4 * N], sum[N], ar[N], ar1[N];
void build_it(int idx, int l, int r) {
  if (l == r) {
    it[idx] = sum[l];
    return;
  }
  build_it(2 * idx, l, (l + r) / 2);
  build_it(2 * idx + 1, (l + r) / 2 + 1, r);
  it[idx] = max(it[2 * idx], it[2 * idx + 1]);
}
void upd(int idx, int l, int r, int lef, int rig, int val) {
  if (l > rig || r < lef) {
    return;
  }
  if (l >= lef && r <= rig) {
    it[idx] += val;
    lazy[idx] += val;
    return;
  }
  if (lazy[idx] != 0) {
    it[2 * idx] += lazy[idx];
    lazy[2 * idx] += lazy[idx];
    it[2 * idx + 1] += lazy[idx];
    lazy[2 * idx + 1] += lazy[idx];
    lazy[idx] = 0;
  }
  upd(2 * idx, l, (l + r) / 2, lef, rig, val);
  upd(2 * idx + 1, (l + r) / 2 + 1, r, lef, rig, val);
  it[idx] = max(it[2 * idx], it[2 * idx + 1]);
}
int get(int idx, int l, int r) {
  if (it[idx] <= 0) {
    return -1;
  }
  if (lazy[idx] != 0) {
    it[2 * idx] += lazy[idx];
    lazy[2 * idx] += lazy[idx];
    it[2 * idx + 1] += lazy[idx];
    lazy[2 * idx + 1] += lazy[idx];
    lazy[idx] = 0;
  }
  if (l == r) {
    return l;
  }
  int i = get(2 * idx + 1, (l + r) / 2 + 1, r);
  if (i != -1) {
    return i;
  }
  return get(2 * idx, l, (l + r) / 2);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, i, j, k, l, type, q;
  cin >> n >> m;
  for (i = 1; i <= n; i++) {
    cin >> ar[i];
    sum[ar[i]]++;
  }
  for (i = 1; i <= m; i++) {
    cin >> ar1[i];
    sum[ar1[i]]--;
  }
  for (i = 1e6; i >= 1; i--) {
    sum[i] += sum[i + 1];
  }
  build_it(1, 1, 1e6);
  cin >> q;
  for (i = 1; i <= q; i++) {
    cin >> type;
    if (type == 1) {
      cin >> j >> k;
      upd(1, 1, 1e6, 1, ar[j], -1);
      ar[j] = k;
      upd(1, 1, 1e6, 1, k, 1);
      if (it[1] <= 0) {
        cout << "-1\n";
      } else {
        cout << get(1, 1, 1e6) << '\n';
      }
    } else {
      cin >> j >> k;
      upd(1, 1, 1e6, 1, ar1[j], 1);
      ar1[j] = k;
      upd(1, 1, 1e6, 1, k, -1);
      if (it[1] <= 0) {
        cout << "-1\n";
      } else {
        cout << get(1, 1, 1e6) << '\n';
      }
    }
  }
}
