题目描述

伞伞 和 小明 在玩一个策略游戏。

有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$，在此基础上定义一个大小为 $n×m$ 的矩阵 $C$，满足 $C_{i,j}=A_i×B_j$。所有下标均从 $1$ 开始。

游戏一共会进行 $q$ 轮，在每一轮中，会给出三个参数，格式如下：

op x y

如果 $op = 1$，则这一轮会进行游戏（游戏轮），伞伞必须从 $[x,y]$ 中选择一个行号 $i$，然后小明再选择一个列号 $j$，那么这一轮中，两人的得分为 $C_{i,j}$。然后，$C_{i,j}$ 在后面的游戏中就不能再被选中了（即伞伞再选择 $i$ 时，小明就不能选 $j$ 了）。如果伞伞选的第 $i$ 行里没有可以选中的位置，则本轮不得分（即得 $0$ 分）。

如果 $op = 2$，则这一轮会进行修改（修改轮），$A_x$ 的值会被修改为 $y$，对应矩阵的第 $x$ 行中没有被选过的位置上的数字会随之发生变化。

伞伞 的目标是使得分尽可能大，小明 的目标是使得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。但是，两人无法预测后面的修改操作，因此两人每次进行游戏时都只会按照当前的最优策略进行。如果当前有多种选择都能获得同样的分数（包括 $0$ 分），伞伞会优先选择行号小的那个。

简言之：

① 如果伞伞选的 $i$ 行中有元素没选过，小明会优先选择没选过的列里 $B_j$ 最小的那个（有多个则任选一个），如果得分为 $0$ ，满足”选取行号最小”原则。

② 如果伞伞选的 $i$ 行中已经没有可选元素，则得分为 $0$,同时与其他得分为 $0$ 的行满足”选取行号最小”原则。

请问：按照二人的最优策略，每个游戏轮的得分是多少？

输入格式

从文件 strat.in 读入数据。 第一行输入三个正整数 $n,m,q$，分别表示数组 $A$，数组 $B$ 的长度和游戏轮数。

第二行：$n$ 个整数，表示 $A_i$，分别表示数组 $A$ 的元素。

第三行：$m$ 个整数，表示 $B_i$，分别表示数组 $B$ 的元素。

接下来 $q$ 行，每行三个正整数 $op,x,y$，表示这一轮的信息。

如果 $op = 1$，则表示游戏轮，伞伞需要从 $[x,y]$ 中选择一行。

如果 $op = 2$，则表示修改轮，$A_x$ 的值会被修改为 $y$。

输入保证至少有一个游戏轮。

输出格式

输出到文件 strat.out。 对于每个游戏轮，另起一行输出一个整数，表示这一轮游戏中，伞伞 和 小明 在最优策略下的得分。

样例1-2

3 2 4
0 1 2
3 4
1 1 3
1 2 3
2 3 6
1 1 3

6
8
3

3 4 5
2 5 4
6 3 4 4
2 2 1
1 1 3
1 2 2
1 1 2
1 1 2

12
3
6
8

解释

在第一组数据中，最优的策略为：

$∙$ 第一个游戏轮，伞伞选择 $3$，小明选择 $1$，得分为 $C_{3,1} = 6$

$∙$ 第二个游戏轮，伞伞选择 $3$，小明选择 $2$，得分为 $C_{3,2} = 8$

$∙$ 第一个修改轮，$A_3$ 被修改成了 $6$，但是第 $3$ 行的所有数字都已经被选过了，故第 $3$ 行后续再选的话得分只能为 $0$

$∙$ 第三个游戏轮，伞伞选择 $2$，小明选择 $1$，得分为 $C_{2,1} = 3$

样例 3-7

见下发文件。

数据规模与约定

下发文件分别对应子任务 $1,2,3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,m,q \leq 2 \times 10^5,0 \leq a_i,b_i \leq 10^9,op \in \{1,2\},1 \leq x \leq y \leq n \space (op = 1),1 \leq x \leq n,0 \leq y \leq 10^9 \space (op = 2)$。输入保证至少有一个游戏轮。