#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
const long long int inf = 9e18;
const long double pi = 2 * acos(0.0);
const int N = 1000005;
int tes, n, m, q;
vector<int> sieve(N, 0);
void si() {
  sieve[1] = 1;
  for (int i = 2; i < N; i++) {
    if (sieve[i] == 0) {
      for (int j = i; j < N; j += i) {
        sieve[j] = i;
      }
    }
  }
}
int power(int x, int y) {
  int res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y >>= 1;
    x = x * x;
  }
  return res;
}
struct node {
  int val = 1e7;
  bool ans = false;
  node() : val(0), ans(false){};
};
struct SegTree {
  int N;
  vector<node> st;
  vector<bool> cLazy;
  vector<int> lazy;
  void init(int n) {
    N = n;
    st.resize(4 * N + 5);
    cLazy.assign(4 * N + 5, false);
    lazy.assign(4 * N + 5, 0);
  }
  void merge(node &cur, node &l, node &r) {
    cur.val = min(l.val, r.val);
    cur.ans = l.ans | r.ans;
  }
  void propagate(int ver, int L, int R) {
    if (L != R) {
      cLazy[ver * 2] = cLazy[ver * 2 + 1] = 1;
      lazy[ver * 2] += lazy[ver], lazy[ver * 2 + 1] += lazy[ver];
    }
    st[ver].val += lazy[ver];
    if (st[ver].val < 0)
      st[ver].ans = true;
    else
      st[ver].ans = false;
    cLazy[ver] = lazy[ver] = 0;
  }
  void build(int ver, int L, int R, vector<int> &a) {
    if (L == R) {
      st[ver].val = a[L - 1];
      if (st[ver].val < 0)
        st[ver].ans = true;
      else
        st[ver].ans = false;
      return;
    }
    int M = (L + R) / 2;
    build(ver * 2, L, M, a), build(ver * 2 + 1, M + 1, R, a);
    merge(st[ver], st[ver * 2], st[ver * 2 + 1]);
  }
  node Query(int ver, int L, int R, int i, int j) {
    if (cLazy[ver]) propagate(ver, L, R);
    if (j < L || i > R) return node();
    if (i <= L && R <= j) return st[ver];
    int M = (L + R) / 2;
    node left = Query(ver * 2, L, M, i, j),
         right = Query(ver * 2 + 1, M + 1, R, i, j), cur;
    merge(cur, left, right);
    return cur;
  }
  void Update(int ver, int L, int R, int i, int j, int val) {
    if (cLazy[ver]) propagate(ver, L, R);
    if (j < L || i > R) return;
    if (i <= L && R <= j) {
      cLazy[ver] = 1, lazy[ver] += val;
      propagate(ver, L, R);
      return;
    }
    int M = (L + R) / 2;
    Update(ver * 2, L, M, i, j, val), Update(ver * 2 + 1, M + 1, R, i, j, val);
    merge(st[ver], st[ver * 2], st[ver * 2 + 1]);
  }
  node query(int l, int r) { return Query(1, 1, N, l, r); }
  void update(int l, int r, int val) { Update(1, 1, N, l, r, val); }
};
void solve() {
  cin >> n >> m;
  vector<int> arr(n), brr(m), cum_d(1e6 + 1, 0);
  ;
  for (int i = 0; i < n; i++) cin >> arr[i];
  ;
  for (int i = 0; i < m; i++) cin >> brr[i];
  ;
  for (int i = 0; i < n; i++) cum_d[arr[i]]--;
  ;
  for (int i = 0; i < m; i++) cum_d[brr[i]]++;
  ;
  for (int i = 1e6 - 1; i > -1; i--) cum_d[i] += cum_d[i + 1];
  SegTree st;
  st.init(1e6 + 1);
  st.build(1, 1, 1e6 + 1, cum_d);
  cin >> q;
  ;
  for (int i = 0; i < q; i++) {
    int t, x, y;
    cin >> t >> x >> y;
    x--;
    if (t == 1) {
      st.update(1, arr[x] + 1, 1);
      arr[x] = y;
      st.update(1, y + 1, -1);
    } else {
      st.update(1, brr[x] + 1, -1);
      brr[x] = y;
      st.update(1, y + 1, 1);
    }
    int l = 1, r = 1e6 + 2, ab = 0;
    while (r > l + 1) {
      int mid = (l + r) / 2;
      node temp = st.query(mid, 1e6 + 1);
      if (temp.ans) {
        l = mid;
        ab = max(ab, mid);
      } else {
        r = mid;
      }
    }
    cout << ab - 1 << "\n";
  }
}
int32_t main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  tes = 1;
  while (tes--) {
    solve();
  }
}
