You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 在暑期举办了一个集训营，最后一次集训营测试，准备让孩子们体验一下 ACM 赛制。众所周知，在 ACM 赛制中，每通过一个题，主办方就会给通过的队伍送一个气球，其中第一个通过某题的队伍还会获得一个一血气球。

小 Z 从 ACM 赛制中想到了一个商机，他在经常举办 ACM 比赛的地方开了一个卖气球的小店。小 Z 的气球店只会售卖两种气球：一血气球和普通气球。每种气球的数量是无限的。

今天，小 Z 的气球店来了 $n$ 位顾客，顾客编号为 $1,2,\cdots,n$，其中第 $i$ 位顾客最多购买 $a_i$ 个一血气球或 $b_i$ 个普通气球。但是，顾客只会购买一种气球，要么买一血气球要么买彩色气球，并且至少买一个气球。

但是，顾客可能有时候因为不同的想法而改变购买气球的需求。而小 Z 是一个强迫症，他强制要求顾客中至少有 $c$ 个人购买他的一血气球，购买一血气球的数量并不做要求。

现在顾客会更改他们的需求 $q$ 次，问，每次顾客的需求更改后小 Z 有多少种方案卖出他的气球。

• 两种不同的方案，当且仅当 $n$ 个顾客中有一个顾客买到的气球的种类不同或者数量不同。

输入格式

从 balloon.in 文件读入数据。

第一行两个整数 $n$ 和 $c$，分别表示顾客数量和小 Z 要求买一血气球的人数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

第三行 $n$ 个整数 $b_1,b_2,\cdots,b_n$。

第四行一个整数 $q$ 表示顾客更改的需求次数。

接下来 $q$ 行，每行三个整数 $i,x,y$，分别表示第 $i$ 个人，他的需求变成了至多购买 $x$ 个一血气球以及 $y$ 个普通气球。

输出格式

输出到 balloon.out 文件。

对于每次更改需求，输出一个正整数，表示方案数，答案对 1e9+7 取模。

样例

2 2
1 1
1 1
1
1 1 1

1

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

4
4

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

66

样例4

此样例满足 $n,q \le 10^3$ 数据范围限制。

点击链接 ex_balloon4.in 和 ex_balloon4.out 下载大样例 4 的输入数据和输出数据。

样例5

此样例满足 $n,q \le 5 * 10^4$ 数据范围限制。

点击链接 ex_balloon5.in 和 ex_balloon5.out 下载大样例 5 的输入数据和输出数据。

样例6

此样例满足 $n,q \le 10^6$ 数据范围限制。

点击链接 ex_balloon6.in 和 ex_balloon6.out 下载大样例 6 的输入数据和输出数据。

说明/提示

样例 2 解释

第一次更改后 $2$ 个人的需求变成了 $(2,2),(2,3)$，又 $c=2$，所以 $ans=2*2=4$。

第二次更改之后 $2$ 个人的需求变成了 $(2,2),(2,2)$ 此时 $ans=2*2=4$ 。

数据范围

测试点 $1$ 的数据，$c=1,q=1$

测试点 $2$ 的数据，$c=1$

测试点 $3$ 的数据，$a_i=b_i=q=1$

测试点 $4,5$ 的数据，$n,q \le 10^3$

测试点 $6,7,8$ 的数据，$n,q \le 5 * 10^4$

测试点 $9,10$ 的数据，$n,q \le 10^6$

所有测试点，满足 $n,q \le 10^6, c \le 20, 1 \le a_i,b_i \le10^8$。