题目描述

小A准备购买一些礼品，奖励模拟赛中表现优秀的同学。

他选定了 $n$ 种礼物，每种礼物都有精装版和普通版。对于第 $i$ 种礼物，若选择精装版，可以购买 $1$ 至 $a_i$ 份；若选择普通版，可以购买 $1$ 至 $b_i$ 份。

每种礼物都必须购买，并且只能选择其中一种版本，不能同时购买两种版本。小A要求至少有 $m$ 种礼物选择精装版。

如果两种购买方案中，至少有一种礼物的版本或购买数量不同，就认为这两种方案不同。

小A会依次提出 $T$ 次修改，每次用三个整数 $op,x,y$ 表示：将第 $op$ 种礼物的精装版数量上限改为 $x$，普通版数量上限改为 $y$。修改会保留，并影响之后的所有修改与询问。

请在每次修改后，求出满足要求的购买方案数。答案对 $10^9+7$ 取模。

输入格式

从文件 buy.in 中读入数据。

第一行包含两个整数 $n,m$，分别表示礼物种数和至少需要选择精装版的礼物种数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始的精装版数量上限。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$，表示初始的普通版数量上限。

第四行包含一个整数 $T$，表示修改次数。

接下来 $T$ 行，每行包含三个整数 $op,x,y$，表示一次修改。

输出格式

输出到文件 buy.out 中。

输出 $T$ 行，每行一个整数，表示对应修改之后的方案数对 $10^9+7$ 取模的结果。

样例 1 输入

2 2
1 2
2 3
2
1 2 2
2 2 2

样例 1 输出

4
4

样例 1 解释

至少有两种礼物选择精装版，而总共只有两种礼物，因此两种礼物都必须选择精装版。

第一次修改后，精装版的数量上限为 $2,2$，共有 $2\times2=4$ 种方案。第二次修改后，这两个上限仍然为 $2,2$，因此答案仍为 $4$。

样例 2 输入

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

样例 2 输出

66
88

样例 3

见选手目录下的 buy/buy3.in 与 buy/buy3.ans。

该样例满足第 $2\sim6$ 个测试点的限制，其中 $n=T=1000,m=10$。

样例 4

见选手目录下的 buy/buy4.in 与 buy/buy4.ans。

该样例满足第 $7\sim8$ 个测试点的限制，其中 $n=T=10^5,m=1$。

样例 5

见选手目录下的 buy/buy5.in 与 buy/buy5.ans。

该样例满足第 $9\sim10$ 个测试点的限制，其中 $n=10^5,m=7,T=1$。初始数量上限均为 $1$，修改后的数量上限不要求为 $1$。

样例 6

见选手目录下的 buy/buy6.in 与 buy/buy6.ans。

该样例满足第 $11\sim20$ 个测试点的限制，其中 $n=T=10^5,m=10$。

数据范围

对于所有测试数据，保证：

• $1\le n,T\le10^5$；
• $1\le m\le10$；
• $1\le a_i,b_i,x,y\le10^8$；
• $1\le op\le n$。

允许 $m>n$，此时没有满足要求的购买方案。

共有 $20$ 个测试点，每个测试点 $5$ 分。各测试点还满足下表中的限制。

测试点编号	特殊限制
$1$	$m=T=1$
$2\sim6$	$n,T\le1000$
$7\sim8$	$m=1$
$9\sim10$	初始 $a_i=b_i=1$，且 $T=1$
$11\sim20$	无特殊限制

第 $9\sim10$ 个测试点只保证初始数组全为 $1$，唯一一次修改的 $x,y$ 可以是通用范围内的任意值。