题目描述
有 $N$ 个人，取红蓝 $2$ 种球。但有些限制：

• 每个人最少取一个球；
• 每个人只能取一种颜色的球；
• 取红球数的人不少于 $C$ 个；
• 第 $i$ 个人最多取 $a_i$ 个红球，最多取 $b_i$ 个蓝球；

请问可能的方案数是多少？

为了增加题目难度，现在每次修改某个人的 $a_i$,$b_i$ 限制，求当前条件下的可能方案数。

输入格式

第一行包含 $2$ 个整数 $N$ 和 $C$，$1 \le N \le 100000$，$1 \le C \le 20$。

第二行有 $N$ 个整数 $a_i$，$1 \le a_i \le 1000000000$。

第三行有 $N$ 个整数 $b_i$，$1 \le b_i \le 1000000000$。

第四行有 $1$ 个整数 $Q$，$1 \le Q \le 100000$，表示有 $Q$ 次修改某个人的 $a_i$,$b_i$ 条件。

下面 $Q$ 行，每行有 $3$ 个整数 $p$、$ap$、$bp$，表示第 $p$ 个人的要求改为红球最多买 $ap$ 个，蓝球最多买 $bp$ 个。$1 \le p \le N$，$1 \le ap \le 1000000000$，$1 \le bp \le 1000000000$。

数据范围

对于 30% 的数据：$1 \le N$， $q \le 1000$ 对于 100% 的数据：$1 \le N$，$q \le 10^6$

输出格式

$Q$ 行，每行一个整数。表示对应当前条件下可能的方案数模 10007 的结果。

样例

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