
/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /&#9680;/   /▐/   /▌/ /▀/ /░/ /&#128293;/   choose  own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/


//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define eb emplace_back
//#define pi 3.14159265358979323846
#define pii pair < ll , int >
#define pipii pair< int, pair < int , int > >
#define siz(n) (int)(n.size())


//namespace fastio {
//    template <class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
//    template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << p.first << " " << p.second; }
//    template <class T> ostream &operator<<(ostream &os, set<T> const& con) { for (auto &u : con) os << u << " "; return os; }
//    void pr() {}
//    template <typename T, typename... args> void pr(T x, args... tail) { cout << x << " "; pr(tail...);}
//}

//using namespace fastio;

const int N = 1048576;
const int MA = 1048576;

int t[N * 4 + 5], c[N], f[N], s[N], ucz[N], jedz[N], add[N * 4 + 5];

void push(int v, bool leaf)
{
    t[v] += add[v];
    if (!leaf)
    {
        add[v << 1] += add[v];
        add[v << 1 | 1] += add[v];
    }
    add[v] = 0;
}

void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] = ucz[tl] - jedz[tl];
        return;
    }

    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    t[v] = min(t[v << 1], t[v << 1 | 1]);
}

int ans;//ответ на solve
void solve(int v, int tl, int tr)
{
    if (tl == tr)
    {
        ans = tl;
        return;
    }

    if (add[v])
        push(v, (tl == tr));
    if (add[v << 1])
        push(v << 1, (tl + 1 == tr));
    if (add[v << 1 | 1])
        push(v << 1 | 1, (tl + 1 == tr));

//    cout<<tl<<" "<<tr<<" "<<t[v << 1]<<" "<<t[v << 1 | 1]<<'\n';
    int tm = (tl + tr) >> 1;
    if (t[v << 1 | 1] < 0)
        solve(v << 1 | 1, tm + 1, tr); else
    if (t[v << 1] < 0)
        solve(v << 1, tl, tm); else
        {
            ans = -1;
            return;
        }
}

void update(int v, int tl, int tr, int l, int r, int wyn)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        add[v] += wyn;
        push(v, (tl == tr));
        return;
    }

    int tm = (tl + tr) >> 1;
    update(v << 1, tl, tm, l, min(tm, r), wyn);
    update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, wyn);
    if (add[v << 1])
        push(v << 1, (tl + 1 == tr));
    if (add[v << 1 | 1])
        push(v << 1 | 1, (tl + 1 == tr));

    t[v] = min(t[v << 1], t[v << 1 | 1]);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Estb_probitie
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n, m;
    cin >> n >> m;
    int a[n], b[m];

    for (int i = 0; i < n; ++i)
        cin >> a[i], f[a[i]]++;

    for (int i = 0; i < m; ++i)
        cin >> b[i], s[b[i]]++;

    for (int i = 1e6; i >= 0; --i)
    {
        jedz[i]+= jedz[i + 1] + f[i];
        ucz[i] += ucz[i + 1]  + s[i];
    }

    build(1, 1, MA);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int co, x;
            cin >> x >> co;
            --x;
            if (co > a[x])
            {
                update(1, 1, MA, a[x] + 1, co, -1);
            } else
            {
                update(1, 1, MA, co + 1, a[x], 1);
            }
            a[x] = co;
        } else
        {
            int co, x;
            cin >> x >> co;
            --x;

            if (co > b[x])
            {
                update(1, 1, MA, b[x] + 1, co, 1);
            } else
            {

                update(1, 1, MA, co + 1, b[x], -1);
            }
            b[x] = co;
        }

        solve(1, 1, MA);
        cout << ans << '\n';
    }



}
