#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 3e5 + 7;
const int A = 1e6;
int n, m, q;
int a[N];
int b[N];
int t[1 << 21], lz[1 << 21];
void apply(int v, int x) {
  t[v] += x;
  lz[v] += x;
}
void push(int v) {
  apply(2 * v, lz[v]);
  apply(2 * v + 1, lz[v]);
  lz[v] = 0;
}
void update(int l1, int r1, int x, int v = 1, int l2 = 0, int r2 = A - 1) {
  if (l1 <= l2 && r2 <= r1) {
    apply(v, x);
    return;
  }
  int m = (l2 + r2) / 2;
  push(v);
  if (l1 <= m) update(l1, r1, x, 2 * v, l2, m);
  if (m < r1) update(l1, r1, x, 2 * v + 1, m + 1, r2);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
int query(int v = 1, int l2 = 0, int r2 = A - 1) {
  if (t[v] >= 0) return -1;
  if (l2 == r2) return l2 + 1;
  int m2 = (l2 + r2) / 2;
  push(v);
  int a = query(2 * v + 1, m2 + 1, r2);
  if (a >= 0)
    return a;
  else {
    return query(2 * v, l2, m2);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
    update(0, a[i], -1);
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
    b[i]--;
    update(0, b[i], +1);
  }
  cin >> q;
  while (q--) {
    int t, i, x;
    cin >> t >> i >> x;
    i--;
    x--;
    if (t == 1) {
      update(0, a[i], 1);
      a[i] = x;
      update(0, a[i], -1);
    } else {
      update(0, b[i], -1);
      b[i] = x;
      update(0, b[i], 1);
    }
    cout << query() << '\n';
  }
}
