Serge来到学校食堂,发现这里排着长队。队列中有 $$$m$$$ 名学生。他现在不确定是否要等到队列清空,所以他想知道如果等待,他会收到哪道菜。由于 Serge 很累,他请你代替他来计算。
最初有 $$$n$$$ 菜肴,成本为 $$$a_1、a_2、\ldots、a_n$$$。如您所知,有 $$$m$$$ 学生的队列,分别有 $$$b_1、\ldots、b_m$$$ togrogs(学生按队列顺序枚举,即队列中的第一个学生有 $$$b_1$$$ togrogs,最后一个学生有 $$$b_m$$$ togrogs)
学生认为最贵的菜就是最好吃的,所以每个学生都只买自己有钱的最贵的菜(每道菜都有一份,所以学生买了之后就没有人可以再买了),如果学生没有钱买任何菜,他就离开队列(太残酷的资本主义……)
但钱对 Serge 来说根本不是问题,所以如果至少剩下一道菜,Serge 就会买最贵的菜。
此外,Serge 的学校经济形势非常不稳定,某些学生的某些菜肴的成本或 togrogs 的数量可能会发生变化。更正式地说,您必须处理 $$$q$$$ 查询:
- 将 $$$a_i$$$ 更改为 $$$x$$$。这意味着第 $$$i$$$ 菜的价格变为 $$$x$$$ togrogs。
- 将 $$$b_i$$$ 更改为 $$$x$$$。这意味着队列中第 $$$i$$$ 个学生现在有 $$$x$$$ 的 togrogs。
在这些查询期间,没有人因为售货员迟到而离开队列。
每次查询后,您必须根据上述规则告诉Serge,如果他等到队列清空,他将购买的菜肴的价格,或者如果此时没有菜肴,则为$$$-1$$$。
输入
第一行包含整数 $$$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$$$。
输出
对于每个 $$$q$$$ 查询,打印语句描述的答案,第 $$$i$$$ 行中第 $$$i$$$ 查询的答案(Serge 将购买的菜肴的价格,如果没有剩余,则为 $$$-1$$$)
示例
输入 #1
1 1 1 1 1 1 1 100
输出 #1
100
输入 #2
1 1 1 1 1 2 1 100
输出 #2
-1
输入 #3
4 6 1 8 2 4 3 3 6 1 5 2 3 1 1 1 2 5 10 1 1 6
输出 #3
8 -1 4
注意
在第一次查询后的第一个样本中,有一个菜品价格为 $$$100$$$ togrogs,而一名学生则有一个 togrogs,因此 Serge 将购买价格为 $$$100$$$ togrogs 的菜品。
在第一次查询后的第二个样本中,有一道菜肴的价格为 1 togrogs,而一名学生的 togrogs 价格为 $$$100$$$,因此 Serge 将一无所获。
在第一次查询后的第三个样本中,没有人可以购买价格为 $$$8$$$ 的菜肴,因此 Serge 将接受它。第二次查询后,所有菜品都会被购买,第三次查询后,第三个和第五个学生将分别购买第一和第二个菜品,而第四个则没有人购买。