题目描述
Calculating the derivative of a polynomial is an easy task. But what about calculating the derivative of 
, where 
is vector? Here we denote 
. To calculate the derivative of , you should know 5 rules:
1. 
, where is a vector here.
2. 
, where 
and 
means to take 
as constants for .
3.
4. 
, where 
is a constant.
5. 
, where 
and is a constant.
Now your task is to calculate the first-derivative of 
for some given .
, where is vector? Here we denote . To calculate the derivative of , you should know 5 rules:
1. , where is a vector here.
2. , where and means to take as constants for .
3.
4. , where is a constant.
5. , where and is a constant.
Now your task is to calculate the first-derivative of for some given .
输入
The first line of the input contains an integer T (T <= 10), indicating the number of cases.
Each test case contains two blocks.
The first line of the first block contains two integers, n and m (0 < n, m <= 100), indicating the number of terms of the polynomial and the dimension of . The next n lines contain m + 1 integers each, Ci, pi1, ..., pim, indicating the coefficient and the exponent of xj of the i-th term.
The first line of the second block contains one integer Q (0 < Q <= 100), indicating the number of queries for the given f(x). Each of the following Q lines contains m integers each, indicating the entry values of .
Note: All the values in the input are nonnegative integers not exceeding 100.
. The next n lines contain m + 1 integers each, Ci, pi1, ..., pim, indicating the coefficient and the exponent of xj of the i-th term.
The first line of the second block contains one integer Q (0 < Q <= 100), indicating the number of queries for the given f(x). Each of the following Q lines contains m integers each, indicating the entry values of .
Note: All the values in the input are nonnegative integers not exceeding 100.
输出
For each query of each test case, output the resulting first-derivative vector in one line, with entries separated by one space and no extra space at the end of the line. For the result may be very big, you are only asked to output each element mod 1000000007.
Add a blank line between two consecutive test cases. There must be no extra blank line at the end of output.
样例输入 Copy
2
3 2
1 2 0
3 0 2
7 0 0
2
1 4
2 3
2 2
1 1 1
9 1 0
2
1 4
2 3
样例输出 Copy
2 24
4 18
13 1
12 2
提示
The first-derivative of the first case is 
.
The first-derivative of the second case is 
.
.
The first-derivative of the second case is .