#include <bits/stdc++.h>
using namespace std;
template <class T>
void MIN(T &A, T B) {
  A = min(A, B);
}
template <class T>
void MAX(T &A, T B) {
  A = max(A, B);
}
template <class T>
void SUM(T &A, T B) {
  A = A + B;
}
template <class T>
void HIEU(T &A, T B) {
  A = A - B;
}
long long n, m, a[300005], b[300005], q;
const long long maxx = int(1e6);
struct phuc {
  long long val, lazy;
} st[maxx * 4 + 5];
void down(long long id) {
  st[id * 2].lazy += st[id].lazy;
  st[id * 2].val += st[id].lazy;
  st[id * 2 + 1].lazy += st[id].lazy;
  st[id * 2 + 1].val += st[id].lazy;
  st[id].lazy = 0;
}
void update(long long id, long long l, long long r, long long u, long long v,
            long long val) {
  if (u > r || v < l) return;
  if (u <= l && v >= r) {
    st[id].val += val;
    st[id].lazy += val;
    return;
  }
  down(id);
  long long mid = (l + r) / 2;
  update(2 * id, l, mid, u, v, val);
  update(2 * id + 1, mid + 1, r, u, v, val);
  st[id].val = min(st[id * 2].val, st[id * 2 + 1].val);
}
long long get(long long id, long long l, long long r) {
  if (l == r) return l;
  down(id);
  long long mid = (l + r) >> 1;
  if (st[id * 2 + 1].val < 0) {
    return get(id * 2 + 1, mid + 1, r);
  }
  if (st[id * 2].val < 0) {
    return get(id * 2, l, mid);
  }
  return -1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i], update(1, 1, maxx, 1, a[i], -1);
  for (int i = 1; i <= m; ++i) cin >> b[i], update(1, 1, maxx, 1, b[i], 1);
  cin >> q;
  while (q--) {
    long long type, l, r;
    cin >> type >> l >> r;
    if (type == 1) {
      update(1, 1, maxx, 1, a[l], 1);
      a[l] = r;
      update(1, 1, maxx, 1, a[l], -1);
    } else {
      update(1, 1, maxx, 1, b[l], -1);
      b[l] = r;
      update(1, 1, maxx, 1, b[l], 1);
    }
    cout << get(1, 1, maxx) << endl;
  }
}
