割草

问题描述

小核桃觉得他的花园中杂草太多了，于是决定把杂草除一除。

花园可以看作一个 $n \times m$ 大小的矩阵，其中第 $i$ 行第 $j$ 列的地的杂草生长速度为每单位时间 $r_{i,j}$。注意，在 $0$ 时间点，花园中没有杂草。

在本题中，会给出两个数组 $\{A_1,A_2,\dots,A_n\}$ 和 $\{B_1,B_2,\dots,B_m\}$，其中 $r_{i,j} = A_i \times B_j$。

接下来小核桃会进行 $q$ 次除草，第 $i$ 次除草发生在 $t_i$ 时间点，每次除草会把某一行或者某一列的所有杂草除掉。除草后 $(i,j)$ 上的杂草依然以 $r_{i,j}$ 的速度生长。

小核桃想知道每次除草除掉的杂草量是多少。由于数据可能过大，所以你需要让答案对 $10^9+7$ 取模后输出。

输入格式

第一行输入用空格隔开的正整数 $n, m$，分别表示花园的大小（$0$ 时刻花园没有杂草）。 第二行输入 $n$ 个整数，第 $i$ 个数表示 $A_i$。 第三行输入 $m$ 个整数，第 $j$ 个数表示 $B_j$。 第四行输入一个正整数 $q$，表示有 $q$ 次除草操作。 接下来 $q$ 行，每行输入形式为以下两种中的一个：

• 1 x t：在 $t$ 时刻除掉所有第 $x$ 行的草。
• 2 y t：在 $t$ 时刻除掉所有第 $y$ 列的草。

输入保证 $t$ 递增。

输出格式

输出 $q$ 行，其中第 $i$ 行表示第 $i$ 次除草除掉的杂草数量，答案需要对 $10^9+7$ 取模。

样例

输入

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

输出

12
15
40
23

样例解释

数据范围与约定

• 对于 20% 的数据：$1 \le n, m, q \le 200$
• 对于 100% 的数据：$1 \le n, m, q \le 10^5$ 且 $0 \le A_i, B_j, t \le 10^9$
• 模数：$10^9+7$