Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4082
Little Sub and his Geometry Problem

Time Limit: 4 Seconds      Memory Limit: 65536 KB

Little Sub loves math very much, and has just come up with an interesting problem when he is working on his geometry homework.

It is very kind of him to share this problem with you. Please solve it with your coding and math skills. Little Sub says that even Mr.Potato can solve it easily, which means it won't be a big deal for you.

The problem goes as follows:

Given two integers $N$ and $K$, and $K$ points $P_1, P_2, \dots, P_K$ with their Euclidean coordinates $(x_1, y_1), (x_2, y_2), \dots, (x_K, y_K)$ on a 2-dimensional plane. Different points may share the same coordinate.

Define the function \[ F(u, v) = \sum_{i=1}^K f(u, v, i) \] where \[ f(u, v, i) = \begin {cases} (u - x_i) + (v - y_i) & u \geq x_i\ \text{and}\ v \geq y_i \\ 0 & \text{otherwise} \end {cases} \]

You are required to solve several queries.

In each query, one parameter $C$ is given and you are required to calculate the number of integer pairs $(u, v)$ such that $1 \leq u,v \leq N$ and $F(u, v) = C $.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 1000$), indicating the number of test cases. For each test case:

The first line contains two positive integers $N$ and $K$ ($1 \le N,K \le 10^5$).

For the following $K$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le N$), indicating the coordinate of the $i$-th point.

The next line contains an integer $Q$ ($1 \le Q \le 10$), indicating the number of queries.

The following line contains $Q$ integers $C_1, C_2 \dots, C_Q$ ($1 \le C_i \le 10^{18}$), indicating the parameters for each query.

It's guaranteed that at most 20 test cases has $N, K \ge 10^4$.

Output

For each test case, output the answers of queries respectively in one line separated by a space.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

Sample Input

2
4 2
1 1
2 3
5
1 2 3 4 5
15 5
1 1 
7 3 
5 10 
8 6 
7 15
3
25 12 31

Sample Output

2 3 4 1 2
5 11 5

Author: TIAN, Wenjie
Source: ZOJ Monthly, January 2019
Submit    Status