CF1179C.Serge and Dining Room

Serge came to the school dining room and discovered that there is a big queue here. There are $m$ pupils in the queue. He's not sure now if he wants to wait until the queue will clear, so he wants to know which dish he will receive if he does. As Serge is very tired, he asks you to compute it instead of him.

Initially there are $n$ dishes with costs $a_1, a_2, \ldots, a_n$. As you already know, there are the queue of $m$ pupils who have $b_1, \ldots, b_m$ togrogs respectively (pupils are enumerated by queue order, i.e the first pupil in the queue has $b_1$ togrogs and the last one has $b_m$ togrogs)

Pupils think that the most expensive dish is the most delicious one, so every pupil just buys the most expensive dish for which he has money (every dish has a single copy, so when a pupil has bought it nobody can buy it later), and if a pupil doesn't have money for any dish, he just leaves the queue (so brutal capitalism...)

But money isn't a problem at all for Serge, so Serge is buying the most expensive dish if there is at least one remaining.

Moreover, Serge's school has a very unstable economic situation and the costs of some dishes or number of togrogs of some pupils can change. More formally, you must process $q$ queries:

• change $a_i$ to $x$. It means that the price of the $i$-th dish becomes $x$ togrogs.
• change $b_i$ to $x$. It means that the $i$-th pupil in the queue has $x$ togrogs now.

Nobody leaves the queue during those queries because a saleswoman is late.

After every query, you must tell Serge price of the dish which he will buy if he has waited until the queue is clear, or $-1$ if there are no dishes at this point, according to rules described above.

谢尔盖来到学校食堂，发现这里排起了长队。队列中一共有 $m$ 名学生。他现在还不确定自己是否愿意等到队伍清空后再打饭，因此他想知道：如果他选择等待，最终会买到哪一道菜。由于谢尔盖非常疲惫，他请你代替他计算这个结果。

初始时共有 $n$ 道菜，价格分别为 $a_1, a_2, \ldots, a_n$。如前所述，队列中有 $m$ 名学生，他们分别拥有 $b_1, \ldots, b_m$ 托格（togrogs）（学生按排队顺序编号，即队首学生有 $b_1$ 托格，队尾学生有 $b_m$ 托格）。

学生们认为最贵的菜就是最美味的，因此每位学生都会购买自己买得起的、价格最高的那道菜（每道菜仅有一份，一旦被某位学生买走，其他人便无法再购买）；若某位学生买不起任何一道菜，则直接离开队伍（如此残酷的资本主义……）

但对谢尔盖而言，金钱根本不是问题——只要还有至少一道菜剩余，他就一定会买下其中最贵的那一道。

此外，谢尔盖所在的学校经济状况极不稳定，某些菜的价格或某些学生的托格数量可能会发生变化。更准确地说，你需要处理 $q$ 个查询：

• 将 $a_i$ 修改为 $x$：表示第 $i$ 道菜的价格变为 $x$ 托格；
• 将 $b_i$ 修改为 $x$：表示队列中第 $i$ 位学生当前拥有 $x$ 托格。

在这些查询执行期间，无人离开队伍（因为售货员迟到了）。

每次查询后，你都需要告诉谢尔盖：若他等到队伍清空后才打饭，根据上述规则，他将买到的那道菜的价格是多少；若此时已无任何菜剩余，则输出 $-1$。

The first line contains integers $n$ and $m$ ($1 \leq n, m \leq 300\ 000$) — number of dishes and pupils respectively. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^{6}$) — elements of array $a$. The third line contains $m$ integers $b_1, b_2, \ldots, b_{m}$ ($1 \leq b_i \leq 10^{6}$) — elements of array $b$. The fourth line conatins integer $q$ ($1 \leq q \leq 300\ 000$) — number of queries.

Each of the following $q$ lines contains as follows:

• if a query changes price of some dish, it contains $1$, and two integers $i$ and $x$ ($1 \leq i \leq n$, $1 \leq x \leq 10^{6}$), what means $a_i$ becomes $x$.
• if a query changes number of togrogs of some pupil, it contains $2$, and two integers $i$ and $x$ ($1 \leq i \leq m$, $1 \leq x \leq 10^{6}$), what means $b_i$ becomes $x$.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300\ 000$），分别表示菜肴数量和学生数量。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{6}$），即数组 $a$ 的元素。
第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_{m}$（$1 \leq b_i \leq 10^{6}$），即数组 $b$ 的元素。
第四行包含一个整数 $q$（$1 \leq q \leq 300\ 000$），表示查询次数。

接下来的 $q$ 行，每行描述如下：

• 若查询为修改某道菜肴的价格，则该行包含整数 $1$，以及两个整数 $i$ 和 $x$（$1 \leq i \leq n$, $1 \leq x \leq 10^{6}$），表示将 $a_i$ 修改为 $x$；
• 若查询为修改某位学生的 togrogs 数量，则该行包含整数 $2$，以及两个整数 $i$ 和 $x$（$1 \leq i \leq m$, $1 \leq x \leq 10^{6}$），表示将 $b_i$ 修改为 $x$。

For each of $q$ queries prints the answer as the statement describes, the answer of the $i$-th query in the $i$-th line (the price of the dish which Serge will buy or $-1$ if nothing remains)

对于每个查询，按照题目描述输出答案：第 $i$ 个查询的答案输出在第 $i$ 行（即谢尔盖将购买的菜肴的价格；若无剩余菜肴，则输出 $-1$）

In the first sample after the first query, there is one dish with price $100$ togrogs and one pupil with one togrog, so Serge will buy the dish with price $100$ togrogs.

In the second sample after the first query, there is one dish with price one togrog and one pupil with $100$ togrogs, so Serge will get nothing.

In the third sample after the first query, nobody can buy the dish with price $8$, so Serge will take it. After the second query, all dishes will be bought, after the third one the third and fifth pupils will by the first and the second dishes respectively and nobody will by the fourth one.

在第一个样例中，第一次查询后，有一道价格为 $100$ 托格的菜肴和一名拥有 $1$ 托格的学生，因此谢尔盖将购买这道价格为 $100$ 托格的菜肴。

在第二个样例中，第一次查询后，有一道价格为 $1$ 托格的菜肴和一名拥有 $100$ 托格的学生，因此谢尔盖将一无所获。

在第三个样例中，第一次查询后，无人能购买价格为 $8$ 的菜肴，因此谢尔盖将取走它。第二次查询后，所有菜肴均被买走；第三次查询后，第三名和第五名学生将分别购买第一道和第二道菜肴，而第四道菜肴无人购买。