卢卡是一个艺术品经销商。他拥有N个客户，并向每位客户销售艺术画。
每个客户可以购买彩色画或黑白画，但不能两者都买。客户i表示，我想购买最多的Ai彩色画和最多Bi黑白画。
客户总是购买至少一幅画。卢卡有几乎无限量的绘画，所以满足客户需要的绘画数量从来不是一个问题。
卢卡不喜欢只卖黑白画，如果小于C个人要彩色画，他会感到悲伤，也不卖画。
他的客户不断地改变他们的要求，即改变他们的要买的绘画数量的上限。正因为如此，卢卡经常被这个问题困扰：“有许多不同的购买方案，使得至少C客户购买至少一副彩色画？“请帮助卢卡。
INPUT
第一行两个数 N, C (1 ≤ N ≤ 100 000, 1 ≤ C ≤ 20).
第二行N个integers ai (1 ≤ ai ≤ 1 000 000 000).
第三行N integers bi (1 ≤ bi ≤ 1 000 000 000).
第四行一个数 Q (1 ≤ Q ≤ 100 000).
接下来Q行，第行三个整数P (1 ≤ P ≤ N), 表示顾客的编号， aP (1 ≤ aP ≤ 1 000 000000) 表示客人想要的彩画的上限 bP (1 ≤ bP ≤ 1 000000 000)表示客人想要的黑白画的上限。
OUTPUT
Q行，每行一个数，表示前面的改变发生后有多少种不同的购买方案（答案对10007求余）
SCORING
In test cases worth 30% of total points, it will hold that N and Q are smaller than 1000.
SAMPLE TESTS

input
2 2
1 1
1 1
1
1 1 1
output
1
input
2 2
1 2
2 3
2
1 2 2
2 2 2
output
4
4
input
4 2
1 2 3 4
1 2 3 4
1
4 1 1
output
66