Description

You are a master of counting. One day, your friend Luka came up with a problem to challenge you.

Luka is a hardworking painter. His paintings are so good that there will be $n$ people who want to buy his paintings.

There are two types of paintings: black-and-white paintings and color paintings.

Luka is very hardworking, so he has infinitely many paintings.

Luka hates selling black-and-white paintings, so he wants at least $c$ people to buy one color painting.

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

However, each customer can only buy either color paintings or black-and-white paintings.

Customers keep changing $a_i$ and $b_i$, and this will happen $q$ times.

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

You need to find, after each change, how many plans Luka has that satisfy all requirements.

To prevent the output from being too large, Luka only needs you to output the number of plans $\bmod\ 10^4+7$.

Input Format

The first line contains two integers $n,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 contain three integers $p_i,a_{p_i},b_{p_i}$. The $i$-th line means that customer $p_i$ changes $a_i$ and $b_i$ to $a_{p_i}$ and $b_{p_i}$.

Output Format

Output $q$ lines, one integer per line. The value on the $i$-th line represents, after the $i$-th change, the number of valid plans $\bmod\ 10^4+7$.

2 2
1 1
1 1
1
1 1 1 

1

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

4
4

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

66

Hint

Sample 1 Explanation

After the first change, we have only one valid plan: sell one color painting to each of the two customers.

Constraints and Limits

• For $30\%$ of the testdata, it is guaranteed that $n,q\le 10^3$.
• For $100\%$ of the testdata, 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 in total.

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

Translated by ChatGPT 5