Problem Description

You are a master of counting, and one day your friend Luka posed a challenging problem to you.

Luka is a diligent painter, and his paintings are so good that $n$ people will come to buy them.

There are two types of paintings: black and white, and colored.

Luka is very industrious, so he has an infinite supply of paintings.

Luka dislikes selling black and white paintings, so he hopes that at least $c$ people will buy a colored painting.

The $i$-th person will buy at most $a_i$ colored paintings and $b_i$ black and white paintings, and they will buy at least one painting.

However, customers can only buy either colored or black and white paintings individually.

Customers will continuously change $a_i$ and $b_i$, and this change will occur $q$ times.

Customers are numbered from $1$ to $n$.

You need to find out how many ways Luka can meet all the requirements after each change.

To prevent the output from being too large, Luka only needs you to tell him the number of ways modulo $10^4 + 7$.

Input Format

The first line contains two integers $n$ and $c$.

The second line contains $n$ integers $a_i$.

The third line contains $n$ integers $b_i$.

The fourth line contains an integer $q$.

The next $q$ lines, each containing three integers $p_i, a_{p_i}, b_{p_i}$, indicate that the customer numbered $p_i$ will change $a_i$ and $b_i$ to $a_{p_i}$ and $b_{p_i}$.

Output Format

There will be $q$ lines, each containing one integer. The $i$-th line's value represents the number of ways to meet the conditions after the $i$-th change, modulo $10^4 + 7$.

Sample Input and Output

Input Sample #1

2 2
1 1
1 1
1
1 1 1

Output Sample #1

1

Input Sample #2

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

Output Sample #2

4
4

Input Sample #3

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

Output Sample #3

66

Notes

Sample 1 Explanation

After the first change, we only have one way, which is to sell a colored painting to both users.

Data Range and Constraints

• For $30\%$ of the data, it is guaranteed that $n, q \le 10^3$.
• For $100\%$ of the data, it is guaranteed that $1 \le n, q \le 10^5$, $1 \le c \le 20$, $1 \le a_i, b_i, a_{p_i}, b_{p_i} \le 10^9$, $1 \le p_i \le n$.

Notes

This problem is worth $140$ points.

This problem is translated from the Croatian Open Competition in Informatics 2015/2016 Contest #1 T5 RELATIVNOST.

见题面 Input 部分

见题面 Output 部分