Robots in Crimea#4550
Crimea is a beautiful place, surrounded on all sides by the sea. Every city has something unique, something that cannot be found anywhere else in the world. There are many resort towns: Sevastopol, Yalta, Yevpatoria, Alushta, Saky, and many more. There are also sites known not only in Ukraine but beyond its borders: Chersonesus, Bakhchisaray, Mangup-Kale, Eski-Kermen. The list could go on for a long time. But for the cities of Crimea to remain so beautiful and attractive, their cleanliness must constantly be maintained, which takes a lot of effort from its residents.
That is why Crimean programmers have invented a special cleaning robot that can efficiently clean each city. Since the robot is very fast, it can manage to maintain cleanliness in many cities, moving almost unnoticed from one to another. However, there is one problem: the robot runs on a special fuel, and it can only be refueled in cities, not on the road between them. We know how many kilometers the robot can travel before needing to refuel. Clearly, a single robot cannot service all cities, because to reach some of them would require traveling a distance exceeding its maximum possible range without refueling.
Assume all roads are parallel to the coordinate axes, so the distance between cities is measured as:
Programmers have already developed models of robots with various fuel tank capacities. For each robot model, the distance it can travel without refueling is known. Now, the question is: how many robots of a given model are needed so that all cities can be serviced?
The first line contains a natural number (1 \leq N \leq 2000)—the number of cities. Each of the following lines contains two integers x_i, y_i—the coordinates of each city. All coordinates are integers and their absolute values do not exceed 10^9.
The next line contains the number (1 \leq M \leq 5 \cdot 10^5)—the number of robot models. Each of the following lines contains one integer (0 \leq K \leq 2 \cdot 10^9), the distance this robot model can travel without refueling.
You may assume that within any city, robots operate on electricity (from trolleybus wires :)), so fuel is only used when traveling between cities.
For each robot model, output a single number—the minimum number of robots of that model needed to service all the cities.
Example
3
4 2
4 5
7 5
2
2
42
1Example 1
In the first query, the robot cannot reach any other city from each city, so robots are needed. In the second query, the robot can reach each city from every other city, so robot is sufficient.