Description
有 N 个人，取红蓝 2 种球。但有些限制：
l 每个人最少取一个球；
l 每个人只能取一种颜色的球；
l 取红球数的人不少于 C 个；
l 第 i 个人最多取 ai 个红球，最多取 bi 个蓝球；
请问可能的方案数是多少？
为了增加题目难度，现在每次修改某个人的 ai,bi 限制，求当前条件下的可能方案数。
Input
第一行包含 2 个整数 N 和 C，1≤N≤100000，1≤C≤20。
第二行有 N 个整数 ai，1≤ai≤1000000000。
第三行有 N 个整数 bi，1≤bi≤1000000000。
第四行有 1 个整数 Q，1≤Q≤100000，表示有 Q 次修改某个人的 ai,bi 条件。
下面 Q 行，每行有 3 个整数 p、ap、bp，表示第 p 个人的要求改为红球最多买 ap 个，蓝球最多买 bp个。1≤p≤N，1≤ap≤1000000000，1≤bp≤1000000000。
Output
Q 行，每行一个整数。表示对应当前条件下可能的方案数模 10007 的结果。
HINT
样例输入2
2 2
1 2
2 3
2
1 2 2
2 2 2
|
样例输出2
4
4
样例输入3
4 2
1 2
3 4
1 2
3 4
1
4 1 1
|
样例输出3
66