Hide

Problem M
Skilaboð

Languages en is
/problems/skilabod/file/statement/en/img-0001.png
Image from Pixabay
You are located in the exact center of the universe at coordinates $(0, 0)$ and want to send a message to every person in the world, and as everyone knows there are only a million people in the world. Unfortunately some transmitters don’t have a very good range. Luckily you have a bunch of different transmitters of different power levels. A transmitter reaches $d$ units away if its power is $d$. That is to say, if the Euclidean distance between you and some other person is not greater than $d$, then that person gets your message. With the help of The Department of National Security you know exactly where everyone is located and now you want to know for each transmitter how many people would get your message if you used that transmitter.

Input

The input begins with a line with a single integer $N$. Next there are $N$ lines with two integers each, $x_i$ and $y_i$, where the values in line $i$ denotes the location of person $i$, $|x_i|, |y_i| \leq 10^9$. Then there is a line with a single integer $Q$. Finally there are $Q$ lines, each with one integer $d_i$ where $d_i$ is the power of transmitter $i$, $0 \leq d_i \leq 10^9$.

Output

$Q$ lines with one integer each, the value in line $i$ giving how many people would receive the message if transmitter $i$ were used.

Scoring

Group

Points

Constraints

1

50

$1 \leq N, Q \leq 1000$

2

50

$1000 < N, Q \leq 10^5$

Sample Input 1 Sample Output 1
5
1 1
2 2
3 2
2 3
4 6
3
1
2
3
0
1
2
Sample Input 2 Sample Output 2
4
-1 10
45 29
-499 -142
599 -10
5
1
29
142
599
1000
0
1
2
3
4

Please log in to submit a solution to this problem

Log in