/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1180E2
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         int[] dishes = readArr(N, infile, st);
         int[] pupils = readArr(M, infile, st);
         RangeTree segtree = new RangeTree();
         for(int x: dishes)
            segtree.update(1, x, -1);
         for(int x: pupils)
            segtree.update(1, x, 1);
         int Q = Integer.parseInt(infile.readLine());
         StringBuilder sb = new StringBuilder();
         while(Q-->0)
         {
            st = new StringTokenizer(infile.readLine());
            int qq = Integer.parseInt(st.nextToken());
            int i = Integer.parseInt(st.nextToken())-1;
            int x = Integer.parseInt(st.nextToken());
            if(qq == 1)
            {
               segtree.update(1, dishes[i], 1);
               segtree.update(1, x, -1);
               dishes[i] = x;
            }
            else
            {
               segtree.update(1, pupils[i], -1);
               segtree.update(1, x, 1);
               pupils[i] = x;
            }
            if(segtree.minQuery(1, 1000000) >= 0)
            {
               sb.append("-1\n");
               continue;
            }
            //location of rightmost negative val
            int low = 1;
            int high = 1000000;
            while(low != high)
            {
               int mid = (low+high+1)/2;
               if(segtree.minQuery(mid, high) >= 0)
                  high = mid-1;
               else
                  low = mid;
            }
            sb.append(low+"\n");
         }
         System.out.print(sb);
      }
      public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
      {
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         return arr;
      }
   }
   class RangeTree 
   {
		private int[] min;
		private int[] lazy;
		private int size;
		public RangeTree() 
      {
			this.size = 1000001;
			min = new int[2100069];
			lazy = new int[2100069];
		}
		public void update(int l, int r, int inc) 
      {
			update(1, 0, size-1, l, r, inc);
		}
		private void pushDown(int index, int l, int r) 
      {
			min[index] += lazy[index];
			if(l != r) 
         {
				lazy[2*index] += lazy[index];
				lazy[2*index+1] += lazy[index];
			}
			lazy[index] = 0;
		}
		private void pullUp(int index, int l, int r) 
      {
			int m = (l+r)/2;
			min[index] = Math.min(evaluateMin(2*index, l, m), evaluateMin(2*index+1, m+1, r));
		}
		private int evaluateMin(int index, int l, int r) 
      {
			return min[index] + lazy[index];
		}
		private void update(int index, int l, int r, int left, int right, int inc) 
      {
			if(r < left || l > right) return;
			if(l >= left && r <= right) {
				lazy[index] += inc;
				return;
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			update(2*index, l, m, left, right, inc);
			update(2*index+1, m+1, r, left, right, inc);
			pullUp(index, l, r);
		}
		public int minQuery(int l, int r) 
      {
			return minQuery(1, 0, size-1, l, r);
		}
		private int minQuery(int index, int l, int r, int left, int right) 
      {
			if(r < left || l > right) return Integer.MAX_VALUE;
			if(l >= left && r <= right) {
				return evaluateMin(index, l, r);
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			int ret = Integer.MAX_VALUE;
			ret = Math.min(ret, minQuery(2*index, l, m, left, right));
			ret = Math.min(ret, minQuery(2*index+1, m+1, r, left, right));
			pullUp(index, l, r);
			return ret;
		}
	}