Works in Crimea
Crimea is a stunning region, surrounded by the sea and home to cities each with their own unique charm, unmatched anywhere else in the world. It boasts numerous resort towns like Sevastopol, Yalta, Yevpatoria, Alushta, Saky, and many more. There are also places of historical significance known far beyond Ukraine's borders, such as Chersonesus, Bakhchisaray, Mangup-Kale, and Eski-Kermen. The list is endless. To keep these cities beautiful and inviting, maintaining their cleanliness is essential, which requires considerable effort from the residents of Crimea.
To address this, Crimean programmers have designed a special cleaning robot capable of swiftly and efficiently tidying up each city. The robot is incredibly fast, able to move almost invisibly from one city to another, ensuring the cities remain clean. However, there's a challenge: the robot runs on a special fuel that can only be replenished in the cities, not while traveling between them. We know the maximum distance it can travel without needing a refuel. Clearly, one robot cannot cover all the cities, as some require traveling distances beyond the robot's range.
Assume all roads are aligned with the coordinate axes, so the distance between cities is calculated as: r = |x_1 - x_2| + |y_1 - y_2|. The programmers have developed M different robot models, each with a distinct fuel tank capacity. For each model, we know the maximum distance it can travel without refueling. The government wants to know: how many robots of a particular model are needed to service all the cities?
Input
The first line contains a natural number N (1 ≤ N ≤ 2000) - the number of cities. Each of the next N lines contains two numbers x_i, y_i – the coordinates of each city. All coordinates are guaranteed to be integers and do not exceed 10^9 in absolute value. Following this is the number M (1 ≤ M ≤ 5·10^5) – the number of robot models available. Each of the subsequent M lines contains one integer K (0 ≤ K ≤ 2·10^9), representing the distance a particular robot model can travel without refueling. It is assumed that within any city, the robot operates on electricity (from trolleybus lines :) ), so fuel is only consumed when traveling between cities.
Output
For each query, output a single number – the minimum number of robots of the specified model needed to service all the cities.