#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 ft[1000010];
int ft2[1000010];
void adjust(int k, int v) {
  for (; k < 1000010; k += (k & (-k))) ft[k] += v;
}
int query(int k) {
  if (k <= 0) return 0;
  int sum = 0;
  for (; k > 0; k -= (k & (-k))) sum += ft[k];
  return sum;
}
void adjust2(int k, int v) {
  for (; k < 1000010; k += (k & (-k))) ft2[k] += v;
}
int query2(int k) {
  if (k <= 0) return 0;
  int sum = 0;
  for (; k > 0; k -= (k & (-k))) sum += ft2[k];
  return sum;
}
int main() {
  setupIO();
  int n, m;
  cin >> n >> m;
  multiset<int> A;
  int AA[n];
  for (int i = 0; i < (n); i++) {
    int x;
    cin >> x;
    A.insert(x);
    AA[i] = x;
  }
  int B[m];
  for (int i = 0; i < (m); i++) cin >> B[i];
  for (int i = 0; i < 1000010; i++) ft[i] = 0;
  ;
  for (int i = 0; i < 1000010; i++) ft2[i] = 0;
  ;
  for (int i = 0; i < (n); i++) {
    adjust2(AA[i], 1);
  }
  for (int i = 0; i < (m); i++) {
    adjust(B[i], 1);
  }
  int q;
  cin >> q;
  for (int i = 0; i < (q); i++) {
    int cmd, tgt, val;
    cin >> cmd >> tgt >> val;
    if (cmd == 1) {
      int oldVal = AA[tgt - 1];
      adjust2(AA[tgt - 1], -1);
      adjust2(val, 1);
      AA[tgt - 1] = val;
      A.erase(A.find(oldVal));
      A.insert(val);
    } else {
      adjust(B[tgt - 1], -1);
      adjust(val, 1);
      B[tgt - 1] = val;
    }
    int lo = 1, hi = 1000010, mid, ans = -1;
    while (lo < hi) {
      mid = (lo + hi) / 2;
      int numChildrenWithMoneyGMid = m - query(mid - 1);
      int numDishesWithCostGMid = n - query2(mid - 1);
      if (numChildrenWithMoneyGMid >= numDishesWithCostGMid) {
        hi = mid;
      } else {
        lo = mid + 1;
        ans = mid;
      }
    }
    if (ans == -1) {
      cout << "-1"
           << "\n";
    } else {
      auto dish = A.lower_bound(ans);
      if (*dish > ans) {
        if (dish == A.begin()) {
          cout << "-1"
               << "\n";
          continue;
        }
        dish--;
      }
      cout << *dish << "\n";
    }
  }
  return 0;
}
