#include <bits/stdc++.h>   using namespace std;   const int MAX_N = 1e6 + 5;   const double delta = 1e-6;   const long long mod = 1e9 + 7;   struct ev {     double coord;     int type;     int mincost;   };   const bool operator<(const ev &f, const ev &s) { return f.coord < s.coord; }   int n, m;   const int magic_const = 2e6;   class segment_tree {    private:     vector<int> a;     vector<int> b;     vector<int> a_left;     vector<int> b_right;     int deltaa, deltab, x, n, now_right;     int answer = 0;     void update_vertex(int v, bool is_leaf) {       if (is_leaf) {         int min_t = min(a[v], b[v]);         a_left[v] = a[v] - min_t;         b_right[v] = b[v] - min_t;       } else {         int l = a_left[v * 2];         int r = b_right[v * 2 + 1];         int min_t = min(l, r);         a_left[v] = l - min_t + a_left[v * 2 + 1];         b_right[v] = r - min_t + b_right[v * 2];       }     }     void build(int v, int l, int r, vector<int> &a1, vector<int> &b1) {       bool leaf = is_leaf(l, r);       if (leaf) {         a[v] = a1[l];         b[v] = b1[l];       } else {         int mid = (l + r) / 2;         build(v * 2, l, mid, a1, b1);         build(v * 2 + 1, mid + 1, r, a1, b1);       }       update_vertex(v, leaf);     }     void update(int v, int l, int r) {       bool leaf = is_leaf(l, r);       if (leaf) {         a[v] += deltaa;         b[v] += deltab;       } else {         int mid = (l + r) / 2;         if (contains_x(l, mid)) update(v * 2, l, mid);         if (contains_x(mid + 1, r)) update(v * 2 + 1, mid + 1, r);       }       update_vertex(v, leaf);     }     void get_answer(int v, int l, int r) {       if (is_leaf(l, r))         answer = l;       else {         int mid = (l + r) / 2;         int now_delta = now_right - a_left[v * 2 + 1];         if (now_delta < 0) {           get_answer(v * 2 + 1, mid + 1, r);         } else {           now_right = now_delta + b_right[v * 2 + 1];           get_answer(v * 2, l, mid);         }       }     }     bool is_leaf(int l, int r) { return l == r; }     bool contains_x(int l, int r) { return x >= l && x <= r; }       public:     segment_tree(vector<int> &a1, vector<int> &b1) {       n = a1.size() - 1;       a.resize(a1.size() * 4);       a_left.resize(a1.size() * 4);       b.resize(b1.size() * 4);       b_right.resize(b1.size() * 4);       build(1, 0, n, a1, b1);     }     void update_ab(int x1, int da, int db) {       x = x1;       deltaa = da;       deltab = db;       update(1, 0, n);     }     int get_answer() {       answer = 0;       now_right = 0;       get_answer(1, 0, n);       if (answer == 0) return -1;       return answer;     }   };   void solve() {     cin >> n >> m;     vector<int> a(MAX_N);     vector<int> b(MAX_N);     a[0] = magic_const;     vector<int> an(n);     vector<int> bm(m);     for (auto &i : an) {       cin >> i;       a[i]++;     }     for (auto &i : bm) {       cin >> i;       b[i]++;     }     segment_tree str(a, b);     int q;     cin >> q;     for (int i = 0; i < q; i++) {       int type, num, x;       cin >> type >> num >> x;       num--;       if (type == 1) {         str.update_ab(an[num], -1, 0);         str.update_ab(x, 1, 0);         an[num] = x;       } else {         str.update_ab(bm[num], 0, -1);         str.update_ab(x, 0, 1);         bm[num] = x;       }       cout << str.get_answer() <<   n ;     }   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     srand(58164);     solve();   }   