题目描述

您是一位计数大师，有一天您的朋友 Luka 出了一道问题来刁难您。

Luka 是一位勤劳的画家，他的画很好，所以会有 $n$ 个人来买他的画。

画分两种，黑白画与彩色画。

Luka 十分勤劳，所以他有无穷多的画。

Luka 讨厌出售黑白画，所以他希望至少有 $c$ 个人会买走一张彩色画。

第 $i$ 个人会至多购买 $a_i$ 张彩色画，$b_i$ 张黑白画，且它们会至少购买一幅画。

但是，客户们只能单独购买彩色画或黑白画。

客户们会不断改变 $a_i$ 与 $b_i$，这种改变会持续 $q$ 次。

客户以 $1\sim n$ 编号。

您需要求出在每次改变之后，Luka 会有几种方案满足所有需求。

为了防止输出太大，Luka 只需要您告诉他方案数 $\bmod\ 10^4+7$ 的值。

输入格式

第一行为两个整数 $n,c$。

第二行为 $n$ 个整数 $a_i$。

第三行为 $n$ 个整数 $b_i$。

第四行为一个整数 $q$。

接下来 $q$ 行，一行三个整数 $p_i,a_{p_i},b_{p_i}$，第 $i$ 行表示标号 $p_i$ 的顾客将 $a_i$ 和 $b_i$ 更换成 $a_{p_i}$ 和 $b_{p_i}$。

输出格式

共 $q$ 行，一行一个整数，第 $i$ 行的值表示进行了第 $i$ 次改变后，满足条件的方案数 $\bmod\ 10^4+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

提示

样例 1 说明

第一次改变后，我们只有唯一的一种方案，就是向两位用户都出售一张彩色画。

数据范围及限制

• 对于 $30\%$ 的数据，保证 $n,q\le 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n,q\le 10^5$，$1\le c\le 20$，$1\le a_i,b_i,a_{p_i},b_{p_i}\le 10^9$，$1\le p_i\le n$。

说明

本题满分 $140$ 分。

本题译自 Croatian Open Competition in Informatics 2015/2016 Contest #1 T5 RELATIVNOST。