该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师准备购买一些礼品奖励模拟赛优秀的同学

他选定了 $n$ 种礼物，每种礼物都有 精装版 和 普通版

徐老师决定对于第 $i$ 种礼物，如果购买 精装版，则最多购买 $a_i$ 份，如果购买 普通版，则最多购买 $b_i$ 份

对于每种礼物，徐老师只会选择一种版本购买，不会两种都买，并且不管选择哪一种版本，他至少会购买一份该种礼物

现在徐老师想知道，在至少购买 $m$ 种 精装版 礼物的前提下，他一共有多少种不同的购买方案？（这里我们认为两种方案中只要有任意一种礼物购买的版本不同或者数量不同，就是不同的方案）

而现在徐老师还没有决定好具体的规划，他会提出 $T$ 次修改，每次修改用 op x y 表示，表示他会将第 $op$ 种礼物的购买数量修改成：精装版 最多购买 $x$ 份，普通版 最多购买 $y$ 份

现在徐老师希望你在每次他修改购物清单后，告诉他现在有多少种不同的购买方案

输入格式

输入第一行包含两个整数 $n,m$ 含义如题

输入第二行包含 $n$ 个整数，分别表示每种礼物 精装版 的购买数量上限 $a_i$

输入第三行包含 $n$ 个整数，分别表示每种礼物 普通版 的购买数量上限 $b_i$

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

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

输出格式

对于每次修改，输出徐老师购买礼物的方案数，由于答案可能很大，请将答案对于 $1e9+7$ 取模

数据范围

对于所有数据满足：$n,T \leq 100000, 1 \leq a_i,b_i \leq 10^8, m \leq 10$

样例输入1

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

样例输出1

4
4

样例解释1

第一次修改后两种礼物的购买数量分别为：$(2,2),(2,3)$，至少购买两种 精装版，则方案数为 $2 * 2=4$

第二次修改后两种礼物的购买数量分别为：$(2,2),(2,2)$，至少购买两种 精装版，则方案数为 $2 * 2=4$

样例输入2

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

样例输出2

66
88