#include <bits/stdc++.h>
using namespace std;
template <class T, class T2>
inline bool chkmax(T &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <class T, class T2>
inline bool chkmin(T &x, const T2 &y) {
  return x > y ? x = y, 1 : 0;
}
template <class T>
inline int sz(T a) {
  return a.size();
}
template <class T, class T2>
inline istream &operator>>(istream &is, pair<T, T2> &p) {
  is >> p.first >> p.second;
  return is;
}
template <class T, class T2>
inline ostream &operator<<(ostream &os, const pair<T, T2> &p) {
  os << p.first << ' ' << p.second;
  return os;
}
template <class T>
inline istream &operator>>(istream &is, vector<T> &v) {
  for (auto &curr : v) is >> curr;
  return is;
}
template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &v) {
  for (auto curr : v) os << curr << ' ';
  return os;
}
void inArray(int a[], const int &n) {
  for (int i = 0; i < n; i++) cin >> a[i];
}
void outArray(int a[], const int &n) {
  for (int i = 0; i < n; i++) cout << a[i] << ' ';
}
const int MAXA = 1e6;
int n, m;
vector<int> a, b;
int st[4 * MAXA + 10], lp[4 * MAXA + 10];
void input() {
  cin >> n >> m;
  a.resize(n);
  b.resize(m);
  cin >> a >> b;
}
void updateLazy(int curr, int cl, int cr) {
  int temp = lp[curr];
  lp[curr] = 0;
  st[curr] += temp;
  if (cl == cr) return;
  lp[curr * 2] += temp;
  lp[curr * 2 + 1] += temp;
}
void update(int curr, int cl, int cr, int l, int r, int val) {
  if (lp[curr] != 0) updateLazy(curr, cl, cr);
  if (cl > r || cr < l) return;
  if (cl >= l && cr <= r) {
    lp[curr] += val;
    updateLazy(curr, cl, cr);
    return;
  }
  int mid = (cl + cr) / 2;
  update(curr * 2, cl, mid, l, r, val);
  update(curr * 2 + 1, mid + 1, cr, l, r, val);
  st[curr] = max(st[curr * 2], st[curr * 2 + 1]);
}
int sum(int curr, int cl, int cr, int l) {
  if (lp[curr] != 0) updateLazy(curr, cl, cr);
  if (cl > l || cr < l) return -MAXA;
  if (cl == cr) return st[curr];
  int mid = (cl + cr) / 2;
  int a = sum(curr * 2, cl, mid, l);
  int b = sum(curr * 2 + 1, mid + 1, cr, l);
  return max(a, b);
}
int firstPositiveElement() {
  int curr = 1;
  int l = 1, r = MAXA;
  if (lp[curr] != 0) updateLazy(curr, l, r);
  while (l != r) {
    int mid = (l + r) / 2;
    if (lp[curr * 2] != 0) updateLazy(curr * 2, l, mid);
    if (lp[curr * 2 + 1] != 0) updateLazy(curr * 2 + 1, mid + 1, r);
    if (st[curr * 2 + 1] > 0) {
      l = mid + 1;
      curr = curr * 2 + 1;
    } else if (st[curr * 2] > 0) {
      r = mid;
      curr = curr * 2;
    } else
      return -1;
  }
  return l;
}
void solve() {
  for (auto id : a) update(1, 1, MAXA, 1, id, 1);
  for (auto id : b) update(1, 1, MAXA, 1, id, -1);
  int q;
  cin >> q;
  while (q--) {
    int t, i, x;
    cin >> t >> i >> x;
    i--;
    if (t == 1) {
      update(1, 1, MAXA, 1, a[i], -1);
      a[i] = x;
      update(1, 1, MAXA, 1, a[i], 1);
    } else {
      update(1, 1, MAXA, 1, b[i], 1);
      b[i] = x;
      update(1, 1, MAXA, 1, b[i], -1);
    }
    cout << firstPositiveElement() << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  return 0;
}
