有 N 个人，取红蓝 2 种球。但有些限制:

每个人最少取一个球；

每个人只能取一种颜色的球；

取红球数的人不少于 C 个；

第 i 个人最多取 ai 个红球，最多取 bi 个蓝球；

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

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

第一行包含 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。

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

【数据范围】

30% 1 ≤ N，q ≤ 1000