#include <bits/stdc++.h>
using namespace std;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
void setupIO(const string &PROB = "") {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  if (PROB.length() != 0) {
    ifstream infile(PROB + ".in");
    if (infile.good()) {
      freopen((PROB + ".in").c_str(), "r", stdin);
      freopen((PROB + ".out").c_str(), "w", stdout);
    }
  }
}
int st[1000010 * 4], lazy[1000010 * 4];
void down(int p, int i, int j) {
  if (lazy[p] == 0) return;
  st[p] += lazy[p];
  if (i != j) {
    lazy[p << 1] += lazy[p];
    lazy[(p << 1) + 1] += lazy[p];
  }
  lazy[p] = 0;
}
void upd(int p, int i, int j, int k, int v) {
  down(p, i, j);
  if (i > k) return;
  if (j <= k) {
    lazy[p] += v;
    return;
  }
  int mid = (i + j) / 2;
  upd(p << 1, i, mid, k, v);
  upd((p << 1) + 1, mid + 1, j, k, v);
  down(p << 1, i, mid);
  down((p << 1) + 1, mid + 1, j);
  st[p] = min(st[(p << 1)], st[(p << 1) + 1]);
}
int qry(int p, int i, int j) {
  down(p, i, j);
  if (st[p] >= 0) return -1;
  if (i == j) return i;
  int right = qry((p << 1) + 1, (i + j) / 2 + 1, j);
  if (right != -1) return right;
  return qry((p << 1), i, (i + j) / 2);
}
int main() {
  setupIO();
  for (int i = 0; i < 1000010 * 4; i++) st[i] = 0;
  ;
  for (int i = 0; i < 1000010 * 4; i++) lazy[i] = 0;
  ;
  int n, m;
  cin >> n >> m;
  int A[n];
  for (int i = 0; i < (n); i++) {
    cin >> A[i];
    upd(1, 0, 1000010, A[i], -1);
  }
  int B[m];
  for (int i = 0; i < (m); i++) {
    cin >> B[i];
    upd(1, 0, 1000010, B[i], 1);
  }
  int q;
  cin >> q;
  for (int i = 0; i < (q); i++) {
    int cmd, tgt, val;
    cin >> cmd >> tgt >> val;
    --tgt;
    if (cmd == 1) {
      upd(1, 0, 1000010, A[tgt], 1);
      A[tgt] = val;
      upd(1, 0, 1000010, A[tgt], -1);
    } else {
      upd(1, 0, 1000010, B[tgt], -1);
      B[tgt] = val;
      upd(1, 0, 1000010, B[tgt], 1);
    }
    cout << qry(1, 0, 1000010) << endl;
  }
  return 0;
}
