#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1000000007;
long long int powermod(long long int _a, long long int _b,
                       long long int _m = mod) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = mod) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = mod) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = mod) {
  return ((a % m) * (b % m)) % m;
}
long long int gcd(long long int a, long long int b) {
  while (a && b) a > b ? a %= b : b %= a;
  return a + b;
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
const int N = 1000010;
int n, m, q, x, y, z, a[300010], b[300010], store[N], mx = 1000000;
struct Segtree {
  static const int MAXN = 1000010;
  struct Node {
    int val;
    int idx;
    int lazy;
    Node() {
      val = 0;
      lazy = 0;
    }
  };
  struct Node tr[4 * MAXN];
  Node Merge(Node a, Node b) {
    struct Node temp;
    if (a.val > b.val) {
      temp.val = a.val;
      temp.idx = a.idx;
    } else {
      temp.val = b.val;
      temp.idx = b.idx;
    }
    temp.lazy = 0;
    return temp;
  }
  void lazyupd(int node, int st, int en) {
    if (st > en) return;
    if (tr[node].lazy == 0) return;
    tr[node].val += tr[node].lazy;
    if (st != en) {
      tr[2 * node].lazy += tr[node].lazy;
      tr[2 * node + 1].lazy += tr[node].lazy;
    }
    tr[node].lazy = 0;
  }
  void Build(int node, int st, int en) {
    if (st == en) {
      tr[node].val = store[st];
      tr[node].idx = st;
      tr[node].lazy = 0;
    } else {
      int mid = (st + en) >> 1;
      Build(2 * node, st, mid);
      Build(2 * node + 1, mid + 1, en);
      tr[node] = Merge(tr[2 * node], tr[2 * node + 1]);
    }
  }
  void Update(int node, int st, int en, int l, int r, int v) {
    lazyupd(node, st, en);
    if (l > en || r < st) return;
    if (l <= st && en <= r) {
      tr[node].lazy += v;
      lazyupd(node, st, en);
      return;
    }
    int mid = (st + en) >> 1;
    Update(2 * node, st, mid, l, r, v);
    Update(2 * node + 1, mid + 1, en, l, r, v);
    tr[node] = Merge(tr[2 * node], tr[2 * node + 1]);
  }
  Node Query(int node, int st, int en) {
    lazyupd(node, st, en);
    if (st == en || tr[node].val <= 0) return tr[node];
    int mid = (st + en) >> 1;
    Node rv = Query(2 * node + 1, mid + 1, en);
    if (rv.val > 0) return rv;
    return Query(2 * node, st, mid);
  }
};
Segtree st;
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  cin >> n >> m;
  for (int i = 0; i < N; i++) store[i] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    store[a[i]]++;
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    store[b[i]]--;
  }
  for (int i = mx - 1; i >= 1; i--) store[i] += store[i + 1];
  st.Build(1, 1, mx);
  cin >> q;
  while (q--) {
    cin >> x >> y >> z;
    if (x == 1) {
      st.Update(1, 1, mx, 1, a[y], -1);
      a[y] = z;
      st.Update(1, 1, mx, 1, a[y], 1);
    } else {
      st.Update(1, 1, mx, 1, b[y], 1);
      b[y] = z;
      st.Update(1, 1, mx, 1, b[y], -1);
    }
    Segtree::Node ans = st.Query(1, 1, mx);
    if (ans.val <= 0) ans.idx = -1;
    cout << ans.idx << endl;
  }
  return 0;
}
