#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
struct LazyMinSegmentTree {
  int sz;
  pair<long long, long long> *tree;
  long long *lazy;
  LazyMinSegmentTree(int s) {
    sz = 1 << (int)ceil(log2(s));
    tree = new pair<long long, long long>[2 * sz];
    lazy = new long long[sz];
    memset(tree, 0, 2 * sz * sizeof(pair<long long, long long>));
    memset(lazy, 0, sz * sizeof(long long));
  }
  LazyMinSegmentTree(int s, pair<long long, long long> *st) {
    sz = 1 << (int)ceil(log2(s));
    tree = new pair<long long, long long>[2 * sz];
    lazy = new long long[sz];
    memset(tree, 0, 2 * sz * sizeof(pair<long long, long long>));
    memset(lazy, 0, sz * sizeof(long long));
    for (int i = 0; i < (s); i++) {
      tree[i + sz] = st[i];
    }
    for (int ind = (sz)-1; ind >= (1); ind--) {
      if (tree[2 * ind].first < 0 && tree[2 * ind + 1].first < 0) {
        if (tree[2 * ind].second < tree[2 * ind + 1].second) {
          tree[ind] = tree[2 * ind];
        } else {
          tree[ind] = tree[2 * ind + 1];
        }
      } else {
        tree[ind] = min(tree[2 * ind], tree[2 * ind + 1]);
      }
    }
  }
  void propagate(int ind) {
    tree[2 * ind].first += lazy[ind];
    tree[2 * ind + 1].first += lazy[ind];
    if (2 * ind < sz) {
      lazy[2 * ind] += lazy[ind];
      lazy[2 * ind + 1] += lazy[ind];
    }
    lazy[ind] = 0;
  }
  void update(int ind, int st, int e, int l, int r, long long v) {
    if (l == st && r == e) {
      tree[ind].first += v;
      if (ind < sz) lazy[ind] += v;
      return;
    }
    propagate(ind);
    int mid = (st + e) / 2;
    if (l < mid) update(2 * ind, st, mid, l, min(r, mid), v);
    if (r > mid) update(2 * ind + 1, mid, e, max(l, mid), r, v);
    if (tree[2 * ind].first < 0 && tree[2 * ind + 1].first < 0) {
      if (tree[2 * ind].second < tree[2 * ind + 1].second) {
        tree[ind] = tree[2 * ind];
      } else {
        tree[ind] = tree[2 * ind + 1];
      }
    } else {
      tree[ind] = min(tree[2 * ind], tree[2 * ind + 1]);
    }
  }
  void update(int a, int b, long long v) { update(1, 0, sz, a, b, v); }
  pair<long long, long long> query(int ind, int st, int e, int l, int r) {
    if (st == l && e == r) return tree[ind];
    propagate(ind);
    int mid = (st + e) / 2;
    if (l < mid && r > mid) {
      pair<long long, long long> p1 = query(2 * ind, st, mid, l, mid);
      pair<long long, long long> p2 = query(2 * ind + 1, mid, e, mid, r);
      if (p1.first < 0 && p2.first < 0) {
        if (p1.second < p2.second) {
          return p1;
        } else {
          return p2;
        }
      } else {
        return min(p1, p2);
      }
    } else if (l < mid)
      return query(2 * ind, st, mid, l, min(mid, r));
    else
      return query(2 * ind + 1, mid, e, max(mid, l), r);
  }
  pair<long long, long long> query(int a, int b) {
    return query(1, 0, sz, a, b);
  }
};
struct SumSegmentTree {
  long long sz;
  long long *tree;
  SumSegmentTree(long long s) {
    sz = 1 << (int)ceil(log2(s));
    tree = new long long[2 * sz];
    memset(tree, 0, 2 * sz * sizeof(long long));
  }
  SumSegmentTree(long long s, long long *st) {
    sz = 1 << (long long)ceil(log2(s));
    tree = new long long[2 * sz];
    memset(tree, 0, 2 * sz * sizeof(long long));
    for (int i = 0; i < (s); i++) {
      tree[i + sz] = st[i];
    }
    for (int ind = (sz)-1; ind >= (1); ind--) {
      tree[ind] = tree[2 * ind] + tree[2 * ind + 1];
    }
  }
  void add(long long ind, long long x) {
    ind += sz;
    tree[ind] += x;
    for (ind /= 2; ind >= 1; ind /= 2) {
      tree[ind] = tree[2 * ind] + tree[2 * ind + 1];
    }
  }
  long long sum(long long a, long long b) {
    a += sz;
    b += sz;
    long long s = 0;
    while (a <= b) {
      if (a % 2 == 1) s += tree[a++];
      if (b % 2 == 0) s += tree[b--];
      a /= 2;
      b /= 2;
    }
    return s;
  }
};
long long n, m, q;
long long arrN[1000005];
long long arrM[1000005];
set<long long> inS;
long long counter[10000005];
pair<long long, long long> feeder[1000005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < (n); i++) {
    cin >> arrN[i];
    if (inS.count(arrN[i]) == 0) {
      inS.insert(arrN[i]);
    }
    counter[arrN[i]]++;
  }
  for (int i = 0; i < (1000005); i++) {
    feeder[i] = make_pair(0, -i);
  }
  LazyMinSegmentTree sgt(1000005, feeder);
  SumSegmentTree sm(1000005, counter);
  sgt.update(0, 1000005, 1000000000);
  for (auto i : inS) {
    sgt.update(i, i + 1, -1000000000 - sm.sum(i, 1000005));
  }
  for (int i = 0; i < (m); i++) {
    cin >> arrM[i];
    sgt.update(0, arrM[i] + 1, 1);
  }
  cin >> q;
  for (int i = 0; i < (q); i++) {
    int a;
    cin >> a;
    if (a == 1) {
      long long b, c;
      cin >> b >> c;
      b--;
      if (sm.tree[sm.sz + arrN[b]] == 1) {
        inS.erase(arrN[b]);
        sgt.update(arrN[b], arrN[b] + 1, 1000000000);
      }
      sm.add(arrN[b], -1);
      arrN[b] = c;
      sm.add(c, 1);
      if (sm.tree[sm.sz + c] == 1) {
        inS.insert(c);
        sgt.update(c, c + 1, -1000000000 - sm.sum(c, 1000005));
      } else {
        sgt.update(c, c + 1, 1);
      }
      sgt.update(0, c, -1);
    } else {
      long long b, c;
      cin >> b >> c;
      b--;
      sgt.update(0, arrM[b] + 1, -1);
      arrM[b] = c;
      sgt.update(0, arrM[b] + 1, 1);
    }
    pair<long long, long long> curAns = sgt.query(0, 1000005);
    if (curAns.first >= 0) {
      cout << -1 << "\n";
    } else {
      cout << -(sgt.query(0, 1000005)).second << "\n";
    }
  }
  return 0;
}
