George's Grass

题号：NC230981
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Besides George Plover's house stands a farm. The farm can be described as an $n\times m$ matrix. The growth rate of weed in row $i$ and column $j$ is denoted as $a_{ij}$ . In this problem, two arrays $\{A_1, A_2, ..., A_n\}$ and $\{B_1, B_2, ..., B_m\}$ will be given. And for all $1\leq i\leq n$ , $1 \leq j\leq m$ , $a_{ij}=A_i \times B_j$ .
The growth rate $a_{ij}$ indicates that the weed will grow $a_{ij}$ units every second. At the moment $0$ , there is no weed on the farm.
George will use mower $q$ times, where the $i$ -th use occurs at the moment $t_i$ . Each use of the mower completely removes weeds in a row or a column.
George wonders how many units of weed he will remove.
The answer might be very large, so please output the desired answer modulo $10^9+7$ .

输入描述:

The first line contains two integers $n$ and $m$ .
The second line contains $n$ integers, where the $i$ -th integer is $A_i$ .
The third line contains $m$ integers, where the $j$ -th integer is $B_j$ .
The next line contains an integer $q$ .
Each of the next $q$ lines contains three integers.
$1$ $x$ $t$ : George clears the weeds in row $x$ at the moment $t$ .

$2$ $y$ $t$ : George clears the weeds in column $y$ at the moment $t$ .

$1\leq n, m, q \leq 10^5$ , $0\leq A_i, B_j \leq 10^{18}$ .
It is guaranteed that $1\leq x \leq n$ , $1 \leq y \leq m$ , $1\leq t\leq 10^{18}$ and $t$ is strictly increasing with lines.

输出描述:

Output one integer indicating the answer modulo .

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

输入

输出

说明