356. The Doctor and the Zygons

0

Easy

The Doctor is engaged in another battle against the Zygons. However, this time he is equipped with a special device that can eliminate all Zygons within its range. The range of the device is not constant and keeps changing. Help the Doctor determine the number of Zygons he can eliminate.

Assume that the Doctor is positioned at the center of a circle. Given N points located on a coordinate plane, where the ith point is located at coordinates (x_i, y_i) representing the position of the ith Zygon, you need to answer Q queries.

In each query, you will be given an integer r_i, which represents the range of the Doctor's special device. By drawing a circle centered at the origin (0,0) with a radius of r_i, you need to determine the number of Zygons that the Doctor can eliminate, i.e. the points that lie inside or on the circumference of this circle.

For each query, print the answer on a new line.

Input Format

The first line contains a single integer N, which represents the number of points on the coordinate plane. Each of the next N lines contains 2 space-separated integers x_i and y_i, representing the x and y coordinates of the ith point. The next line contains a single integer Q, which represents the number of queries. Each of the next Q lines contains a single integer, where the integer on the ith line represents the parameter of the ith query r_i.

Output Format

For each query, print the answer on a new line.

Example

Input

5 1 1 2 2 3 3 -1 -1 4 4 2 3 32

Output

3 5

Constraints

1 <= N <= 10^5
-10^9 <= x_i ,y_i <= 10^9
1 <= Q <= 10^5
1 <= r_i <= 10^18
Loading...

View Submissions

Console