#include <bits/stdc++.h>
using namespace std;
template <typename T>
using V = vector<T>;
template <typename T>
struct SegTree {
  vector<int> sz;
  vector<T> st;
  vector<T> lz;
  T e = 0;
  T id = -1e9;
  T lze = 0;
  int n;
  SegTree(int _sz, vector<int> &A) {
    n = _sz;
    sz.resize(4 * n, 0), st.resize(4 * n, e), lz.resize(4 * n, lze);
    build(n, A);
  }
  void push(int p, int L, int R) {
    if (lz[p] != lze) {
      st[p] += lz[p];
      if (L < R) {
        lz[p << 1] += lz[p];
        lz[p << 1 | 1] += lz[p];
      }
      lz[p] = lze;
    }
  }
  T merge(T L, T R) { return max(L, R); }
  void pull(int p) {
    sz[p] = sz[p << 1] + sz[p << 1 | 1];
    st[p] = merge(st[p << 1], st[p << 1 | 1]);
  }
  void build(int siz, vector<int> &A) {
    for (int i = 0; i < (n << 2); i++) {
      lz[i] = lze, st[i] = e;
    }
    build(1, 0, siz - 1, A);
  }
  void build(int p, int L, int R, vector<int> &A) {
    if (L == R) {
      sz[p] = 1;
      st[p] = A[L];
      return;
    }
    build(p << 1, L, (L + R) >> 1, A);
    build(p << 1 | 1, ((L + R) >> 1) + 1, R, A);
    pull(p);
  }
  void upd(int l, int r, T val) { upd(1, l, r, 0, n - 1, val); }
  void upd(int p, int l, int r, int L, int R, T val) {
    push(p, L, R);
    if (l > R || r < L) return;
    if (l <= L && r >= R) {
      lz[p] += val;
      push(p, L, R);
      return;
    }
    upd(p << 1, l, r, L, (L + R) >> 1, val);
    upd(p << 1 | 1, l, r, ((L + R) >> 1) + 1, R, val);
    pull(p);
  }
  T query(int l, int r) { return query(1, l, r, 0, n - 1); }
  T query(int p, int l, int r, int L, int R) {
    push(p, L, R);
    if (l > R || r < L) return id;
    if (l <= L && r >= R) return st[p];
    return merge(query(p << 1, l, r, L, (L + R) >> 1),
                 query(p << 1 | 1, l, r, ((L + R) >> 1) + 1, R));
  }
  T best(int p, int L, int R) {
    push(p, L, R);
    if (L == R) {
      return st[p] > 0 ? L : -1;
    }
    int left = st[p << 1] + lz[p << 1],
        right = st[(p << 1) | 1] + lz[(p << 1) | 1];
    if (right > 0) {
      return best(p << 1 | 1, ((L + R) >> 1) + 1, R);
    }
    return best(p << 1, L, (L + R) >> 1);
  }
};
const int MM = 1e6 + 5;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(m);
  vector<int> cnt(MM, 0);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
    cnt[b[i]]--;
  }
  for (int i = MM - 2; i >= 0; i--) {
    cnt[i] += cnt[i + 1];
  }
  SegTree<int> seg(MM, cnt);
  int q;
  cin >> q;
  while (q--) {
    int t, i, y;
    cin >> t >> i >> y;
    i--;
    if (t == 1) {
      if (a[i] < y) {
        seg.upd(a[i] + 1, y, +1);
      } else {
        seg.upd(y + 1, a[i], -1);
      }
      a[i] = y;
    } else {
      if (b[i] < y) {
        seg.upd(b[i] + 1, y, -1);
      } else {
        seg.upd(y + 1, b[i], +1);
      }
      b[i] = y;
    }
    cout << seg.best(1, 0, MM - 1) << '\n';
  }
  cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
  return 0;
}
