#include <bits/stdc++.h>
const long double pi = acos(-1.0);
const long double eps = 1e-9;
using namespace std;
const int N = 1e6 + 100;
const int M = 1e6;
pair<int, int> t[4 * N];
int n, m;
int a[N], b[N], cnt[N];
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v].first = t[v].second = a[tl];
  } else {
    int tm = (tl + tr) >> 1;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v].first = t[v * 2].first + t[v * 2 + 1].first;
    t[v].second =
        max(t[v * 2 + 1].second, t[v * 2].second + t[v * 2 + 1].first);
  }
}
void update(int v, int tl, int tr, int pos, int x) {
  if (tl == tr)
    t[v].first = t[v].second = x;
  else {
    int tm = (tl + tr) >> 1;
    if (pos <= tm)
      update(v * 2, tl, tm, pos, x);
    else
      update(v * 2 + 1, tm + 1, tr, pos, x);
    t[v].first = t[v * 2].first + t[v * 2 + 1].first;
    t[v].second =
        max(t[v * 2 + 1].second, t[v * 2].second + t[v * 2 + 1].first);
  }
}
int get(int v, int tl, int tr, int x) {
  if (tl == tr) {
    return tl;
  } else {
    int tm = (tl + tr) >> 1;
    if (t[v * 2 + 1].second + x >= 1)
      get(v * 2 + 1, tm + 1, tr, x);
    else
      get(v * 2, tl, tm, x + t[v * 2 + 1].first);
  }
}
void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    update(1, 1, M, a[i], cnt[a[i]] + 1);
    cnt[a[i]]++;
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    update(1, 1, M, b[i], cnt[b[i]] - 1);
    cnt[b[i]]--;
  }
  int q;
  cin >> q;
  while (q--) {
    int type, l, r;
    cin >> type >> l >> r;
    if (type == 1) {
      cnt[a[l]]--;
      update(1, 1, M, a[l], cnt[a[l]]);
      a[l] = r;
      cnt[a[l]]++;
      update(1, 1, M, a[l], cnt[a[l]]);
    } else {
      cnt[b[l]]++;
      update(1, 1, M, b[l], cnt[b[l]]);
      b[l] = r;
      cnt[b[l]]--;
      update(1, 1, M, b[l], cnt[b[l]]);
    }
    if (t[1].second < 1)
      cout << -1 << "\n";
    else
      cout << get(1, 1, M, 0) << "\n";
  }
}
int main() {
  ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(10);
  int step;
  step = 1;
  for (int i = 1; i <= step; i++) {
    solve();
  }
}
