#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int n1, long long int n2) {
  if (n2 != 0)
    return gcd(n2, n1 % n2);
  else
    return n1;
}
long long int power(long long int a, long long int b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  long long int x = power(a, b / 2);
  if (b & 1) {
    return a * x * x;
  }
  return x * x;
}
int tree[4 * (1000005)], lazy[4 * (1000005)];
void push(int ind, int l, int r) {
  if (lazy[ind] == 0) return;
  tree[ind] += lazy[ind];
  if (l != r) {
    lazy[2 * ind] += lazy[ind];
    lazy[2 * ind + 1] += lazy[ind];
  }
  lazy[ind] = 0;
}
void upd(int ind, int l, int r, int left, int right, int val) {
  push(ind, l, r);
  if (left > r || l > right) return;
  if (left <= l && r <= right) {
    lazy[ind] += val;
    push(ind, l, r);
    return;
  }
  int mid = (l + r) / 2;
  upd(ind * 2, l, mid, left, right, val);
  upd(ind * 2 + 1, mid + 1, r, left, right, val);
  tree[ind] = min(tree[2 * ind], tree[2 * ind + 1]);
}
int que(int ind, int l, int r) {
  push(ind, l, r);
  if (tree[ind] >= 0) return -1;
  if (l == r) return l;
  int mid = (l + r) / 2;
  int res = que(2 * ind + 1, mid + 1, r);
  if (res != -1) return res;
  que(2 * ind, l, mid);
}
int main() {
  int n, m;
  cin >> n >> m;
  int a[300005], b[300005];
  memset(tree, 0, sizeof(tree));
  memset(lazy, 0, sizeof(lazy));
  for (__typeof((n)) i = (1); i <= (n); i++) {
    cin >> a[i];
    upd(1, 1, (1000000 + 5) - 1, 1, a[i], -1);
  }
  for (__typeof((m)) i = (1); i <= (m); i++) {
    cin >> b[i];
    upd(1, 1, (1000000 + 5) - 1, 1, b[i], 1);
  }
  int t;
  cin >> t;
  while (t--) {
    int i, j, k;
    cin >> i >> j >> k;
    if (i == 1) {
      upd(1, 1, (1000000 + 5) - 1, 1, a[j], 1);
      a[j] = k;
      upd(1, 1, (1000000 + 5) - 1, 1, a[j], -1);
    } else {
      upd(1, 1, (1000000 + 5) - 1, 1, b[j], -1);
      b[j] = k;
      upd(1, 1, (1000000 + 5) - 1, 1, b[j], 1);
    }
    cout << que(1, 1, (1000000 + 5) - 1) << "\n";
  }
}
