
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;


#define LETS_GET_SCHWIFTY ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
#define ff              first
#define ss              second
//#define int             long long
#define ll              long long
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)      __builtin_ctzll(x)
#define mod             998244353
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define vpii            vector<pair<int,int> >
#define all(x)          x.begin(),x.end()
#define matrixprint(arr,a,b,c,d) for(int i=a;i<=c;i++){for(int j=b;j<=d;j++){cout<<arr[i][j]<<" ";}cout<<"\n";}
#define show(arr,x,y)   for(int i=x;i<=y;i++){cout<<arr[i]<<" ";}cout<<"\n"
#define sz(x)           (int)x.size()
#define db(x)           cout<<x<<"\n";

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//insert,find_by_order,order_of_key,lower_bound,upper_bound;

#define TRACE
#ifdef TRACE
#define deb(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define deb(...)
#endif

  
//////////////////////////////code//////////////////////////////

const int N = 1e6 + 5;

int n,m;
vi a,b;

struct data
{
  //Use required attributes
  int mx;
 
  //Default Values
  data() : mx(-1e9) {};
};


vector<int> pref(N+5);

 
struct SegTree
{
  
  vector<data> st;
  vector<bool> cLazy;
  vector<int> lazy;
 
  void init()
  {

    st.resize(4 * N + 5);
    cLazy.assign(4 * N + 5, false);
    lazy.assign(4 * N + 5, 0);
  }
 
  //Write reqd merge functions
  void merge(data &cur, data &l, data &r) 
  {
    cur.mx = max(l.mx, r.mx);
   // deb(cur.mx,l.mx,r.mx);
  }
  
  //Handle lazy propagation appriopriately
  void propagate(int node, int L, int R)
  {
    if(L != R)
    {
      cLazy[node*2] = 1;
      cLazy[node*2 + 1] = 1;
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node]; 
    }
    st[node].mx += lazy[node];
    cLazy[node] = 0;
    lazy[node] = 0;
  }
 
  void build(int node, int L, int R)
  {
    if(L == R)
    {
      st[node].mx = pref[L];
     // deb(st[node].mx,L);
      return;
    }
    int M = (L + R) / 2;
    build(node*2, L, M);
    build(node*2 + 1, M + 1, R);
    merge(st[node], st[node*2], st[node*2+1]);
  }
 
  data Query(int node, int L, int R, int i, int j)
  {
    if(cLazy[node])
      propagate(node, L, R);
    if(j<L || i>R)
      return data();
    if(i<=L && R<=j)
      return st[node];
    int M = (L + R)/2;
    data left = Query(node*2, L, M, i, j);
    data right = Query(node*2 + 1, M + 1, R, i, j);
    data cur;
    merge(cur, left, right);
    return cur;
  }
 
  data pQuery(int node, int L, int R, int pos)
  {
    if(cLazy[node])
      propagate(node, L, R);
    if(L == R)
      return st[node];
    int M = (L + R)/2;
    if(pos <= M)
      return pQuery(node*2, L, M, pos);
    else
      return pQuery(node*2 + 1, M + 1, R, pos);
  } 
 
  void Update(int node, int L, int R, int i, int j, int val)
  {
    if(cLazy[node])
      propagate(node, L, R);
    if(j<L || i>R)
      return;
    if(i<=L && R<=j)
    {
      cLazy[node] = 1;
      lazy[node] += val;
      propagate(node, L, R);
      return;
    }
    int M = (L + R)/2;
    Update(node*2, L, M, i, j, val);
    Update(node*2 + 1, M + 1, R, i, j, val);
    merge(st[node], st[node*2], st[node*2 + 1]);
  }
 
  void pUpdate(int node, int L, int R, int pos, int val)
  {
    if(cLazy[node])
      propagate(node, L, R);
    if(L == R)
    {
      cLazy[node] = 1;
      lazy[node] += val;
      propagate(node, L, R);
      return;
    }
    int M = (L + R)/2;
    if(pos <= M)
      pUpdate(node*2, L, M, pos, val);
    else
      pUpdate(node*2 + 1, M + 1, R, pos, val);
    merge(st[node], st[node*2], st[node*2 + 1]);
  }
 
  data query(int pos)
  {
    return pQuery(1, 1, N, pos);
  }
 
  data query(int l, int r)
  {
    return Query(1, 1, N, l, r);
  }
 
  void update(int pos, int val)
  {
    pUpdate(1, 1, N, pos, val);
  }
 
  void update(int l, int r, int val)
  {
    Update(1, 1, N, l, r, val);
  }
};


void solve()
{

    cin>>n>>m;

    a = vi(n+1);
    b = vi(m+1);
  

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

    for(int i=1;i<=m;i++) cin>>b[i],pref[b[i]]--;

    for(int i=N-1;i>=1;i--)
      pref[i]+=pref[i+1];


    SegTree st;
    st.init();
    st.build(1,1,N-1);

    int q;
    cin>>q;

    while(q--)
    {
        int t;
        cin>>t;

        if(t == 1)
        {
            int idx,x;
            cin>>idx>>x;

            st.update(1,a[idx],-1);
            st.update(1,x,1);
            a[idx]=x;

        }
        else 
        {
            int idx,x;
            cin>>idx>>x;

            st.update(1,b[idx],1);
            st.update(1,x,-1);
            b[idx]=x;

        }
          
       int l=1,h=1e6,ans=-1;

       while(l<=h)
       {
            int mid = (l+h)>>1;

            if(st.query(mid,1e6).mx > 0)
            {
               ans = mid;
               l=mid+1;
            }
            else
              h=mid-1;
       }

       cout<<ans<<"\n";
    }

   
}

int32_t main()
{   

    LETS_GET_SCHWIFTY;

     #ifndef ONLINE_JUDGE
     freopen("INP.txt", "r", stdin);
     freopen("out.txt", "w", stdout);
     #endif  


    int t = 1;
  // cin >> t;

    while (t--)
        solve();

}

// check out for following mistakes-
// if using pb operation on vector and then trying to access index..check if sizeof that vec could remain 0 only
// is using prime sieve make sure it fits
// when using factorial template or combinatorics make sure that you edit fillfac fun values and array values

