年轻的 Luka 是一名艺术品商人。他有 $N$ 个客户，并向每个客户出售艺术画作。

每个客户可以购买彩色画作或黑白画作，但不能同时购买两者。

编号为 $i$ 的客户最多想购买 $a_i$ 幅彩色画作，且最多想购买 $b_i$ 幅黑白画作。

每个客户总是会购买至少一幅画作。Luka 拥有几乎无限数量的画作，因此客户所需的画作数量永远不是问题。

Luka 不喜欢出售黑白画作，他知道如果得到彩色画作的人数少于 $C$ 人，他会感到难过。

他的客户不断改变他们的需求，换句话说，即他们想要购买的画作数量。因此，Luka 经常被一个问题所困扰：“有多少种不同的购买方案，使得至少有 $C$ 个客户获得至少一幅彩色画作？”请帮助 Luka，为他排忧解难。

输入格式

输入的第一行包含两个整数 $N, C$ ($1 \le N \le 100\,000$, $1 \le C \le 20$)。

第二行包含 $N$ 个整数 $a_i$ ($1 \le a_i \le 1\,000\,000\,000$)。

第三行包含 $N$ 个整数 $b_i$ ($1 \le b_i \le 1\,000\,000\,000$)。

第四行包含需求变更的次数 $Q$ ($1 \le Q \le 100\,000$)。

接下来的 $Q$ 行，每行包含三个整数，表示改变需求的客户编号 $P$ ($1 \le P \le N$)，他最多想购买的彩色画作数量 $a_P$ ($1 \le a_P \le 1\,000\,000\,000$)，以及他最多想购买的黑白画作数量 $b_P$ ($1 \le b_P \le 1\,000\,000\,000$)。

输出格式

输出必须包含 $Q$ 行，每行包含一个整数，表示在当前需求下，满足条件的购买方案数模 $10\,007$ 的值。

子任务

在占总分 30% 的测试数据中，满足 $N$ 和 $Q$ 均小于 $1000$。

样例

输入 1

2 2
1 1
1 1
1
1 1 1

输出 1

1

输入 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

说明

第一个样例的解释：在第一个客户将他的需求从 $(1, 1)$ 更改为 $(1, 1)$ 之后——实际上什么都没有改变，出售画作的方案数是 $1$。唯一的一种出售方案是向第一个客户出售一幅彩色画作，向第二个客户也出售一幅彩色画作。每个客户都被要求获得至少一幅彩色画作，因为 $C=2$，这意味着必须有至少 $2$ 个客户获得彩色画作。