#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
const int N = 3e5 + 5;
const int INF = 1e6 + 5;
const int mod = 1000000007;
const double Pi = acos(-1);
void Fastio() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
int n, m;
int ST[4 * INF], a[N], b[N], V[INF], lz[4 * INF];
void Build(int node, int l, int r) {
  if (l == r) {
    ST[node] = V[l];
    return;
  }
  int mid = (l + r) >> 1;
  Build(node << 1, l, mid);
  Build(node << 1 | 1, mid + 1, r);
  ST[node] = max(ST[node << 1], ST[node << 1 | 1]);
}
void Push(int node, int l, int r) {
  if (lz[node] == 0) {
    return;
  }
  ST[node] += lz[node];
  if (l != r) {
    lz[node << 1] += lz[node];
    lz[node << 1 | 1] += lz[node];
  }
  lz[node] = 0;
}
void Update(int node, int l, int r, int L, int R, int x) {
  Push(node, l, r);
  if (r < L or l > R) {
    return;
  }
  if (L <= l and r <= R) {
    lz[node] += x;
    Push(node, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  Update(node << 1, l, mid, L, R, x);
  Update(node << 1 | 1, mid + 1, r, L, R, x);
  ST[node] = max(ST[node << 1], ST[node << 1 | 1]);
}
int Get(int node, int l, int r) {
  Push(node, l, r);
  if (l == r) {
    if (ST[node] > 0) {
      return l;
    } else {
      return 0;
    }
  }
  if (ST[node] <= 0) {
    return 0;
  }
  int mid = (l + r) >> 1;
  int temp = Get(node << 1 | 1, mid + 1, r);
  if (temp) {
    return temp;
  } else {
    return Get(node << 1, l, mid);
  }
}
int main() {
  Fastio();
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    V[a[i]]++;
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    V[b[i]]--;
  }
  n = 1e6;
  for (int i = n - 1; i >= 1; i--) {
    V[i] += V[i + 1];
  }
  Build(1, 1, n);
  int q;
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      int id, x;
      cin >> id >> x;
      Update(1, 1, n, 1, a[id], -1);
      a[id] = x;
      Update(1, 1, n, 1, a[id], 1);
    } else {
      int id, x;
      cin >> id >> x;
      Update(1, 1, n, 1, b[id], 1);
      b[id] = x;
      Update(1, 1, n, 1, b[id], -1);
    }
    int temp = Get(1, 1, n);
    if (temp == 0) {
      cout << -1 << '\n';
    } else {
      cout << temp << '\n';
    }
  }
}
