#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], val[N], mx = 1000000;
int tree[4 * N], idx[4 * N], lazy[4 * N];
void merge(int node) {
  if (tree[2 * node] > tree[2 * node + 1]) {
    tree[node] = tree[2 * node];
    idx[node] = idx[2 * node];
  } else {
    tree[node] = tree[2 * node + 1];
    idx[node] = idx[2 * node + 1];
  }
}
void build(int node = 1, int st = 1, int en = mx) {
  if (st == en) {
    tree[node] = val[st];
    idx[node] = st;
    lazy[node] = 0;
    return;
  }
  int mid = (st + en) >> 1;
  build(2 * node, st, mid);
  build(2 * node + 1, mid + 1, en);
  merge(node);
}
void push_down(int node, int st, int en) {
  if (lazy[node] == 0) return;
  tree[node] += lazy[node];
  if (st != en) {
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
  }
  lazy[node] = 0;
}
void update(int node, int st, int en, int l, int r, int val) {
  if (st > r || en < l) return;
  push_down(node, st, en);
  if (l <= st && en <= r) {
    tree[node] += val;
    if (st != en) {
      lazy[2 * node] += val;
      lazy[2 * node + 1] += val;
    }
    return;
  }
  int mid = (st + en) >> 1;
  update(2 * node, st, mid, l, r, val);
  update(2 * node + 1, mid + 1, en, l, r, val);
  merge(node);
}
pair<int, int> query(int node = 1, int st = 1, int en = mx) {
  push_down(node, st, en);
  if (tree[node] <= 0 || st == en) return {tree[node], idx[node]};
  int mid = (st + en) >> 1;
  auto rv = query(2 * node + 1, mid + 1, en);
  if (rv.first > 0) return rv;
  return query(2 * node, st, mid);
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  cin >> n >> m;
  for (int i = 0; i < N; i++) val[i] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    val[a[i]]++;
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    val[b[i]]--;
  }
  for (int i = mx - 1; i >= 1; i--) val[i] += val[i + 1];
  build();
  cin >> q;
  while (q--) {
    cin >> x >> y >> z;
    if (x == 1) {
      update(1, 1, mx, 1, a[y], -1);
      a[y] = z;
      update(1, 1, mx, 1, a[y], 1);
    } else {
      update(1, 1, mx, 1, b[y], 1);
      b[y] = z;
      update(1, 1, mx, 1, b[y], -1);
    }
    auto ans = query();
    if (ans.first <= 0) ans.second = -1;
    cout << ans.second << endl;
  }
  return 0;
}
