#include<bits/stdc++.h>

#define TASK "text"
#define all(x) x.begin(), x.end()
#define compact(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define fi first
#define se second
#define ___Speacial_ signed main()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> Ii;
typedef pair<int, ll> iI;
typedef vector<int> vi;
typedef vector<ii> vii;
template<class T> using minHeap = 
priority_queue<T, vector <T>, greater<T>>;

const int N = 3e5 + 5;
const int maxn = 1e6 + 7;

struct node {
    int sum; int mSuf;
    node (int _val = 0) : sum(_val), mSuf(_val) { } 
} tree[maxn * 4 + 2];
int a[maxn + 2], b[maxn + 2];
int d[maxn + 2];

int n, m, nQueries;

node operator + (const node &left, const node &right) {
    node newNode;
    newNode.sum = left.sum + right.sum;
    newNode.mSuf = max(left.mSuf + right.sum, right.mSuf);
    return newNode;
}

void build(int id, int l, int r) {
    if (l == r) {
        tree[id] = d[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);

    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

void modify(int id, int l, int r, int pos, int delta) {
    if (l == r) {
        tree[id].sum += delta;
        tree[id].mSuf += delta;
        return;
    }

    int mid = (l + r) >> 1;
    if (pos <= mid) modify(id << 1, l, mid, pos, delta);
        else modify(id << 1 | 1, mid + 1, r, pos, delta);

    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

int walk(int id, int l, int r, int sum) {
    if (tree[id].mSuf + sum <= 0) return -1;
    if (l == r) return l;

    int mid = (l + r) >> 1;
    int res = walk(id << 1 | 1, mid + 1, r, sum);
    if (res != -1) return res;
    return walk(id << 1, l, mid, sum + tree[id << 1 | 1].sum);
}

void process(void) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; d[a[i]]++;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> b[i]; d[b[i]]--;
    }

    build(1, 1, maxn);
    cin >> nQueries; 
    while (nQueries--) {
        int type, i, val;
        cin >> type >> i >> val;

        if (type & 1) {
            modify(1, 1, maxn, a[i], -1);
            modify(1, 1, maxn, a[i] = val, +1);
        }

        else {
            modify(1, 1, maxn, b[i], +1);
            modify(1, 1, maxn, b[i] = val, -1);
        }

        cout << walk(1, 1, maxn, 0) << '\n';
    }
}

___Speacial_ {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(TASK".inp","r")){
        freopen(TASK".inp","r",stdin);
        freopen(TASK".out","w",stdout);
    }
    int testcases = 1; //    cin >> testcases;
    for (int o_O = 1; o_O <= testcases; ++o_O) {
//        cout << "Case #" << o_O << ":\n"; 
        process();
        if (o_O != testcases) cout << '\n';
    }

    cerr << "[Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms.]\n";
    return (0 ^ 0);
}