#include <bits/stdc++.h>
using namespace std;
struct fast_ios {
  fast_ios() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
  for (long long i = 0; i < v.size(); i++) {
    cout << v[i];
    if (i != v.size() - 1) cout << endl;
  };
  return os;
}
template <typename T>
void Out(T x) {
  cout << x << endl;
}
template <typename T1, typename T2>
void Ans(bool first, T1 y, T2 n) {
  if (first)
    Out(y);
  else
    Out(n);
}
using vec = vector<long long>;
using mat = vector<vec>;
using Pii = pair<long long, long long>;
using PiP = pair<long long, Pii>;
using PPi = pair<Pii, long long>;
using bools = vector<bool>;
using pairs = vector<Pii>;
const long long mod = 1000000007;
struct LazySegmentTree {
  using T_A = long long;
  using T_B = long long;
  T_A id_A = -1000000000000000000;
  T_B id_B = 0;
  long long N;
  vector<T_A> dat;
  vector<T_B> ope;
  T_A F_AA(T_A &u, T_A &v) { return max(u, v); }
  T_A F_AB(T_A &u, T_B &v, long long sz) { return u + v; }
  T_B F_BB(T_B &u, T_B &v) { return u + v; }
  LazySegmentTree(long long n) {
    N = 1;
    while (n > N) N = N << 1;
    dat = vector<T_A>(2 * N - 1, id_A);
    ope = vector<T_B>(2 * N - 1, id_B);
  }
  LazySegmentTree(long long n, vector<T_A> &v) {
    N = 1;
    while (n > N) N = N << 1;
    dat = vector<T_A>(2 * N - 1, id_A);
    ope = vector<T_B>(2 * N - 1, id_B);
    for (long long i = (0); i < (n); i++) dat[i + N - 1] = v[i];
    for (long long i = (N - 1) - 1; i >= (0); i--)
      dat[i] = F_AA(dat[i * 2 + 1], dat[i * 2 + 2]);
  }
  void eval(long long k, long long l, long long r) {
    if (ope[k] != id_B) {
      dat[k] = F_AB(dat[k], ope[k], r - l);
      if (r - l > 1) {
        ope[k * 2 + 1] = F_BB(ope[k * 2 + 1], ope[k]);
        ope[k * 2 + 2] = F_BB(ope[k * 2 + 2], ope[k]);
      }
      ope[k] = id_B;
    }
  }
  void update(long long a, long long b, T_B x, long long k, long long l,
              long long r) {
    eval(k, l, r);
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      ope[k] = F_BB(ope[k], x);
      eval(k, l, r);
    } else {
      update(a, b, x, k * 2 + 1, l, (l + r) / 2);
      update(a, b, x, k * 2 + 2, (l + r) / 2, r);
      dat[k] = F_AA(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  T_A get(long long a, long long b, long long k, long long l, long long r) {
    if (r <= a || b <= l) return id_A;
    eval(k, l, r);
    if (a <= l && r <= b)
      return dat[k];
    else {
      T_A vl = get(a, b, k * 2 + 1, l, (l + r) / 2);
      T_A vr = get(a, b, k * 2 + 2, (l + r) / 2, r);
      return F_AA(vl, vr);
    }
  }
  void update(long long a, long long b, T_B x) { update(a, b, x, 0, 0, N); }
  T_A get(long long a, long long b) { return get(a, b, 0, 0, N); }
  T_A val(long long k) { return get(k, k + 1); }
};
signed main() {
  long long n, m;
  cin >> n >> m;
  vec a(n);
  cin >> a;
  vec b(m);
  cin >> b;
  long long q;
  cin >> q;
  vec ans(q);
  const long long N = 1000000;
  vec ini(N + 1, 0);
  for (long long i = (0); i < (n); i++) ini[a[i]]++;
  for (long long i = (0); i < (m); i++) ini[b[i]]--;
  for (long long i = (N)-1; i >= (0); i--) ini[i] += ini[i + 1];
  LazySegmentTree ST(N + 1, ini);
  long long t, i0, x;
  for (long long i = (0); i < (q); i++) {
    cin >> t >> i0 >> x;
    i0--;
    if (t == 1) {
      ST.update(0, a[i0] + 1, -1);
      a[i0] = x;
      ST.update(0, a[i0] + 1, 1);
    } else {
      ST.update(0, b[i0] + 1, 1);
      b[i0] = x;
      ST.update(0, b[i0] + 1, -1);
    }
    if (ST.get(0, N + 1) <= 0)
      ans[i] = -1;
    else {
      long long A0 = 0, A1 = N + 1;
      while (A1 - A0 > 1) {
        long long A = (A0 + A1) / 2;
        if (ST.get(A, N + 1) > 0)
          A0 = A;
        else
          A1 = A;
      }
      ans[i] = A0;
    }
  }
  for (long long i = (0); i < (q); i++) cout << ans[i] << '\n';
  return 0;
}
