#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
using namespace std;
int n, q, aa[300005], bb[300006], m;
vector<int> a(1000005), lazy(4 * 1000005);
vector<int> seg(4 * 1000005);
void build(int cur, int st, int end) {
  if (st == end) {
    seg[cur] = a[st];
    return;
  }
  int mid = (st + end) >> 1;
  build(2 * cur, st, mid);
  build(2 * cur + 1, mid + 1, end);
  seg[cur] = max(seg[2 * cur], seg[2 * cur + 1]);
}
void updaterange(int cur, int st, int end, int l, int r, int val) {
  if (lazy[cur] != 0) {
    seg[cur] += lazy[cur];
    if (st != end) {
      lazy[2 * cur] += lazy[cur];
      lazy[2 * cur + 1] += lazy[cur];
    }
    lazy[cur] = 0;
  }
  if (st > end || st > r || end < l) return;
  if (l <= st && end <= r) {
    seg[cur] += val;
    if (st != end) {
      lazy[2 * cur] += val;
      lazy[2 * cur + 1] += val;
    }
    return;
  }
  int mid = (st + end) >> 1;
  updaterange(2 * cur, st, mid, l, r, val);
  updaterange(2 * cur + 1, mid + 1, end, l, r, val);
  seg[cur] = max(seg[2 * cur], seg[2 * cur + 1]);
}
int query(int cur, int st, int end, int l, int r) {
  if (st > end || st > r || end < l) return -1;
  if (lazy[cur] != 0) {
    seg[cur] += lazy[cur];
    if (st != end) {
      lazy[2 * cur] += lazy[cur];
      lazy[2 * cur + 1] += lazy[cur];
    }
    lazy[cur] = 0;
  }
  if (st == end) {
    if (seg[cur] > 0)
      return st;
    else
      return -1;
  }
  if (seg[cur] <= 0) return -1;
  int mid = (st + end) >> 1;
  int ans2 = query(2 * cur + 1, mid + 1, end, l, r);
  if (ans2 >= 0) return ans2;
  int ans1 = query(2 * cur, st, mid, l, r);
  return ans1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) {
    int i, j, k, l, c[1000005];
    cin >> n >> m;
    for (i = 0; i < n; i++) {
      cin >> aa[i];
    }
    for (j = 0; j < m; j++) cin >> bb[j];
    for (i = 0; i <= 1000004; i++) a[i] = 0, c[i] = 0;
    for (i = 0; i < m; i++) {
      a[bb[i]]--;
    }
    for (i = 1000000; i >= 0; i--) a[i] = (a[i] + a[i + 1]);
    for (i = 0; i < n; i++) {
      c[aa[i]]++;
    }
    for (i = 1000000; i >= 0; i--) c[i] = (c[i] + c[i + 1]);
    for (i = 0; i <= 1000000; i++) a[i] = (a[i] + c[i]);
    build(1, 1, 1000000);
    cin >> q;
    while (q--) {
      int che, ind, x;
      cin >> che;
      if (che == 1) {
        cin >> ind >> x;
        ind--;
        updaterange(1, 1, 1000000, 1, aa[ind], -1);
        updaterange(1, 1, 1000000, 1, x, 1);
        int kk = query(1, 1, 1000000, 1, 1000000);
        cout << kk << '\n';
        aa[ind] = x;
      } else {
        cin >> ind >> x;
        ind--;
        updaterange(1, 1, 1000000, 1, bb[ind], 1);
        updaterange(1, 1, 1000000, 1, x, -1);
        int kk = query(1, 1, 1000000, 1, 1000000);
        cout << kk << '\n';
        bb[ind] = x;
      }
    }
  }
  return 0;
}
