import java.io.*;

public class MAIN {

    public static final int maxn = (int)3e5 + 5;
    public static int n = 0, m = 0;
    public static int[] a = new int[maxn];
    public static int[] b = new int[maxn];


    public static aInt[] T = new aInt[(int)1 << 21];

    static public void Update(int idx, int low, int high, int pos, int val) {
        if(T[idx] == null) T[idx] = new aInt();
        if(low == high){
            T[idx].Sum += val;
            T[idx].minSum += val;
            return;
        }
        int avg = (low + high) / 2;
        if (pos <= avg)
            Update(idx + idx, low, avg, pos, val);
        else
            Update(idx + idx + 1, avg + 1, high, pos, val);
        if(T[idx + idx] == null) T[idx + idx] = new aInt();
        if(T[idx + idx + 1] == null) T[idx + idx + 1] = new aInt();
        T[idx].Sum = T[idx + idx].Sum + T[idx + idx + 1].Sum;
        T[idx].minSum = Math.min(T[idx + idx].minSum + T[idx + idx + 1].Sum, T[idx + idx + 1].minSum);
    }

    static public void Update(int pos, int val){
        Update(1, 1, 1000000, pos, val);
    }

    static public int Query(int idx, int suffSum, int left, int right){
        if (T[idx].minSum + suffSum >= 0){
            return -1;
        }else if (left == right){
            return left;
        }else{
            int avg = (left + right) / 2;
            int q2 = Query(idx + idx + 1, suffSum, avg + 1, right);
            if (q2 == -1){
                return Query(idx + idx, T[idx + idx + 1].Sum + suffSum, left, avg);
            }else {
                return q2;
            }
        }
    }

    static public int Query(){
        return Query(1, 0, 1, 1000000);
    }

    static public void main(String[] args) throws IOException {
        BufferedReader bis = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = bis.readLine();
        String[] s = input.split("\\s");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        input = bis.readLine();
        s = input.split("\\s");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s[i]);
            Update(a[i], -1);
        }
        input = bis.readLine();
        s = input.split("\\s");
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(s[i]);
            Update(b[i], +1);
        }
        input = bis.readLine();
        int q = Integer.parseInt(input);
        while(q-- > 0)
        {
            int com, i, x;
            input = bis.readLine();
            s = input.split("\\s");
            com = Integer.parseInt(s[0]);
            i = Integer.parseInt(s[1]);
            x = Integer.parseInt(s[2]);
            --i;
            if (com == 1){
                Update(a[i], +1);
                a[i] = x;
                Update(a[i], -1);
            }else{
                Update(b[i], -1);
                b[i] = x;
                Update(b[i], +1);
            }
            out.write(Integer.toString(Query()) + '\n');
        }
        out.flush();
    }
}
class aInt{
    int Sum;
    int minSum;
    public aInt(){
        Sum = 0;
        minSum = 0;
    }
}