#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool checkMin(T& a, T b) {
  return (a > b ? a = b, 1 : 0);
}
template <class T>
inline bool checkMax(T& a, T b) {
  return (a < b ? a = b, 1 : 0);
}
const int N = 1000005;
struct Node {
  int t, m;
  Node *l, *r;
  Node() {
    t = 0;
    l = r = NULL;
  }
  ~Node() {
    if (l != NULL) delete l;
    if (r != NULL) delete r;
  }
  void pushUp() {
    m = min(l->m, r->m);
    ;
  }
  void pushDown() {
    l->t += t;
    r->t += t;
    l->m += t;
    r->m += t;
    t = 0;
  }
};
struct STree {
  Node* R;
  STree() { R = new Node(); }
  void build(int l, int r, Node* p = NULL) {
    if (p == NULL) p = R;
    if (l == r) {
      p->m = 0;
      return;
    }
    int m = (l + r) >> 1;
    build(l, m, p->l = new Node());
    build(m + 1, r, p->r = new Node());
    p->pushUp();
  }
  void modify(int l, int r, int ul, int ur, int d, Node* p = NULL) {
    ;
    ;
    ;
    ;
    ;
    if (p == NULL) p = R;
    if (ul != ur) p->pushDown();
    if (ul >= l && ur <= r) {
      p->t += d;
      p->m += d;
      return;
    }
    int m = (ul + ur) >> 1;
    if (l <= m) modify(l, r, ul, m, d, p->l);
    if (r > m) modify(l, r, m + 1, ur, d, p->r);
    p->pushUp();
  }
  int query(int l, int r, Node* p = NULL) {
    if (p == NULL) p = R;
    if (l != r) p->pushDown();
    ;
    if (p->m >= 0) return -1;
    if (l == r) return l;
    int m = (l + r) >> 1;
    if (p->r->m < 0)
      return query(m + 1, r, p->r);
    else
      return query(l, m, p->l);
  }
  ~STree() { delete R; }
};
int n, m;
int d[N], p[N];
STree st;
const int E = 1000001;
void init() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &d[i]);
  for (int i = 0; i < m; i++) scanf("%d", &p[i]);
  st.build(0, E);
  for (int i = 0; i < m; i++) st.modify(0, p[i], 0, E, 1);
  for (int i = 0; i < n; i++) st.modify(0, d[i], 0, E, -1);
}
void solve() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int opt, id, nv;
    scanf("%d%d%d", &opt, &id, &nv);
    id--;
    if (opt == 1) {
      st.modify(0, d[id], 0, E, 1);
      st.modify(0, d[id] = nv, 0, E, -1);
    } else {
      st.modify(0, p[id], 0, E, -1);
      st.modify(0, p[id] = nv, 0, E, 1);
    }
    printf("%d\n", st.query(0, E));
  }
}
int main() {
  init();
  solve();
  return 0;
}
