#include <bits/stdc++.h>
using namespace std;
int lazy[(1 << 21) + 1], tree[(1 << 21)];
int N, M;
int siz = (1 << 20);
int A[300001], B[300001];
void propagate(int node, int L, int R) {
  tree[node] += lazy[node];
  if (L != R) {
    lazy[node * 2] += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
  }
  lazy[node] = 0;
}
void update(int node, int L, int R, int i, int j, int val) {
  propagate(node, L, R);
  if (L > R || L > j || R < i) return;
  if (L >= i && R <= j) {
    lazy[node] += val;
    propagate(node, L, R);
    return;
  }
  if (L != R && lazy[node] != 0) propagate(node, L, R);
  update(node * 2, L, (L + R) / 2, i, j, val);
  update(node * 2 + 1, (L + R) / 2 + 1, R, i, j, val);
  tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}
int ind;
int query(int node, int L, int R, int i, int j) {
  if (L > R || L > j || R < i) return 0;
  if (lazy[node] != 0) {
    tree[node] += lazy[node];
    if (L != R) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
  if (L >= i && R <= j) return tree[node];
  int q1 = query(node * 2, L, (L + R) / 2, i, j);
  int q2 = query(node * 2 + 1, (L + R) / 2 + 1, R, i, j);
  return min(q1, q2);
}
multiset<int> st1, st2;
void insert(int x) {
  if (N <= M) return;
  if ((int)st1.size() == N && x < *st1.begin())
    st2.insert(x);
  else {
    st1.insert(x);
    if ((int)st1.size() == N + 1) {
      st2.insert(*st1.begin());
      st1.erase(st1.find(*st1.begin()));
    }
  }
}
void delet(int x) {
  if (N <= M) return;
  if (x < *st1.begin())
    st2.erase(st2.find(x));
  else {
    st1.erase(st1.find(x));
    if (!st2.empty()) {
      st1.insert(*st2.rbegin());
      st2.erase(st2.find(*st2.rbegin()));
    }
  }
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
    insert(A[i]);
    update(1, 0, siz - 1, 0, A[i] - 1, -1);
  }
  for (int i = 1; i <= M; i++) {
    scanf("%d", &B[i]);
    update(1, 0, siz - 1, 0, B[i] - 1, 1);
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a == 1) {
      delet(A[b]);
      insert(c);
      update(1, 0, siz - 1, 0, A[b] - 1, 1);
      A[b] = c;
      update(1, 0, siz - 1, 0, A[b] - 1, -1);
    } else {
      update(1, 0, siz - 1, 0, B[b] - 1, -1);
      B[b] = c;
      update(1, 0, siz - 1, 0, B[b] - 1, 1);
    }
    ind = -1;
    int low = -1, high = 1000001, mid;
    while (low + 1 < high) {
      mid = (low + high) / 2;
      if (query(1, 0, siz - 1, mid, siz - 1) < 0)
        low = mid;
      else
        high = mid;
    }
    ind = low;
    if (ind == -1) {
      if (N <= M)
        printf("-1\n");
      else
        printf("%d\n", *st2.rbegin());
    } else
      printf("%d\n", ind + 1);
  }
  return 0;
}
