• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

---

Hadi is an art dealer. He has N clients and sells artistic paintings to each client. Each client can purchase either colored paintings or black and white paintings, but not both. The client denoted with i wants to purchase at most $a_i$ colored paintings and at most $b_i$ black and white paintings.

The client will always purchase \textbf{at least one} paintings. Hadi has an almost unlimited amount of paintings, so the number of paintings required from the clients is never a problem. Hadi doesn’t like selling black and white paintings and knows that if less than \textbf{C} people get colored paintings, it will make him feel sad.

His clients constantly keep changing their requests or, in other words, the number of paintings they want to purchase. Because of this, Hadi is often troubled by the question: “How many different purchases are there, so that at least C clients get at least one colored painting?” Help Hadi and save him from his worries.

Input

The first line of input contains two integers N, C.

The second line of input contains N integers $a_i$.

The third line of input contains N integers $b_i$.

The fourth line of input contains the number of requirement changes Q.

Each of the following Q lines contains three integers, the label of the person changing the requirements P, the maximal number of colored paintings they want to purchase $a_p$ and the maximal number of black and white paintings they want to purchase $b_p$.

Output

The output must consist of Q lines where each line contains the number of different purchases modulo 10007.

Constraints

• $1 \leq N,Q \leq 10^5 $
• $1 \leq a_i,b_i,a_p,b_p \leq 10^9 $
• $1 \leq C \leq 20 $

Sample Test Data

input 1

2 2
1 2
2 3
2
1 2 2
2 2 2

output 1

4
4

input 2

4 2
1 2 3 4
1 2 3 4
1
4 1 1

output 2

66