#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 7, INF = 1e9 + 7, LIM = 1e6;
int it[4 * LIM + 7] = {}, lz[4 * LIM + 7] = {}, n, m, a[MAXN], b[MAXN], q;
void lp(int g) {
  if (lz[g]) {
    it[g * 2] += lz[g], it[g * 2 + 1] += lz[g];
    lz[g * 2] += lz[g], lz[g * 2 + 1] += lz[g];
    lz[g] = 0;
  }
}
void update(int g, int l, int r, int c, int delta) {
  if (l > c) return;
  if (r <= c) return lz[g] += delta, it[g] += delta, void();
  lp(g);
  int mid = (l + r) >> 1;
  update(g * 2, l, mid, c, delta), update(g * 2 + 1, mid + 1, r, c, delta);
  it[g] = min(it[g * 2], it[g * 2 + 1]);
  return;
}
int query(int g, int l, int r, int d) {
  if (r < d) return INF;
  if (d <= l) return it[g];
  lp(g);
  int mid = (l + r) >> 1;
  return min(query(g * 2, l, mid, d), query(g * 2 + 1, mid + 1, r, d));
}
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];
  for (int i = 1; i <= m; ++i) cin >> b[i];
  for (int i = 1; i <= n; ++i) update(1, 1, LIM, a[i], -1);
  for (int i = 1; i <= m; ++i) update(1, 1, LIM, b[i], 1);
  cin >> q;
  while (q--) {
    int tp, pos, x;
    cin >> tp >> pos >> x;
    int pre = a[pos], delta = -1;
    if (tp == 2) pre = b[pos], delta = 1;
    update(1, 1, LIM, pre, -delta);
    update(1, 1, LIM, x, delta);
    int l = 1, r = LIM, res = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (query(1, 1, LIM, mid) < 0)
        res = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    cout << res << '\n';
  }
  return 0;
}
