#include <bits/stdc++.h>
using namespace std;
struct SumSegmentTree {
 private:
  vector<int> v;
  vector<int> u;
  int n;
  const int NULL_VALUE = 0;

 public:
  SumSegmentTree(int num) {
    v.resize((1 << (int)(ceil(log2(num)) + 1)) - 1, NULL_VALUE);
    u.resize(v.size(), NULL_VALUE);
    n = v.size() / 2;
  }
  SumSegmentTree(vector<int> &source) {
    v.resize((1 << (int)(ceil(log2(source.size())) + 1)) - 1, NULL_VALUE);
    u.resize(v.size(), NULL_VALUE);
    n = v.size() / 2;
    for (int i = 0; i < source.size(); i++) {
      v[i + n] = source[i];
    }
    for (int i = n - 1; i >= 0; i--) {
      updateNode(i);
    }
  }

 private:
  int left(int i) { return i * 2 + 1; }
  int right(int i) { return i * 2 + 2; }
  int parent(int i) { return (i - 1) / 2; }
  int mergeValues(int v1, int v2) { return max(v1, v2); }
  void updateNode(int i) { v[i] = mergeValues(v[left(i)], v[right(i)]); }
  void lazyUpdate(int i) {
    if (u[i] != 0) {
      v[i] += u[i];
      if (i < v.size() / 2) {
        u[left(i)] += u[i];
        u[right(i)] += u[i];
      }
      u[i] = 0;
    }
  }
  int rangeQuery(int i, int l, int r, int a, int b) {
    lazyUpdate(i);
    if (l >= a && r <= b) {
      return v[i];
    }
    if (r < a || l > b) {
      return NULL_VALUE;
    }
    int m = (l + r) / 2;
    return mergeValues(rangeQuery(left(i), l, m, a, b),
                       rangeQuery(right(i), m + 1, r, a, b));
  }
  void updateToRoot(int i) {
    updateNode(i);
    if (i != 0) {
      updateToRoot(parent(i));
    }
  }
  void rangeAdd(int i, int a, int b, int l, int r, int off) {
    lazyUpdate(i);
    if (l >= a && r <= b) {
      u[i] += off;
      lazyUpdate(i);
    } else if (!(r < a || l > b)) {
      int m = (l + r) / 2;
      rangeAdd(left(i), a, b, l, m, off);
      rangeAdd(right(i), a, b, m + 1, r, off);
      updateNode(i);
    }
  }

 public:
  int rangeSum(int a, int b) { return rangeQuery(0, 0, n, a, b); }
  void update(int index, int value) {
    int i = n + index;
    v[i] = value;
    updateToRoot(parent(i));
  }
  void rangeUpdate(int a, int b, int offset) {
    rangeAdd(0, a, b, 0, n, offset);
  }
  void sol(int i) {
    if (i >= v.size() / 2) {
      cout << i - v.size() / 2 << "\n";
      return;
    }
    lazyUpdate(i);
    lazyUpdate(left(i));
    lazyUpdate(right(i));
    if (v[i] <= 0) {
      cout << -1 << "\n";
      return;
    }
    if (v[right(i)] > 0) {
      sol(right(i));
    } else {
      sol(left(i));
    }
  }
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> v(1e6 + 1);
  vector<int> aa(n);
  vector<int> bb(m);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    aa[i] = a;
    v[a]++;
  }
  for (int i = 0; i < m; i++) {
    int a;
    cin >> a;
    bb[i] = a;
    v[a]--;
  }
  for (int i = 1e6 - 1; i >= 0; i--) {
    v[i] = v[i] + v[i + 1];
  }
  int q;
  cin >> q;
  SumSegmentTree st(v);
  for (int i = 0; i < q; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    b--;
    if (a == 1) {
      st.rangeUpdate(0, aa[b], -1);
      st.rangeUpdate(0, c, +1);
      aa[b] = c;
    } else {
      st.rangeUpdate(0, bb[b], +1);
      st.rangeUpdate(0, c, -1);
      bb[b] = c;
    }
    st.sol(0);
  }
}
