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

Output Format

Example

Input

Output

Constraints

-10^9 <= x_i ,y_i <= 10^9

1 <= Q <= 10^5

1 <= r_i <= 10^18

View Submissions

Console