Radioactivity

A nuclear power plant is both a blessing and a curse of modern civilization. It carries many dangers, yet it is also the cheapest way to generate electricity. In this problem we consider the situation created by two nuclear power plants that stand close to each other.

Assume the ground is completely flat and every house lies on a 2D coordinate plane. The two plants are located at $(a_x, a_y)$ and $(b_x, b_y)$. Any location whose distance from plant $(a_x, a_y)$ is at most $R_1$ (the boundary at distance exactly $R_1$ is included) is a high-risk radiation zone. Likewise, any location whose distance from plant $(b_x, b_y)$ is at most $R_2$ is also a high-risk radiation zone.

The plant operators hand out one piece of protective equipment to each house in a high-risk zone. Therefore a house that lies in the high-risk zones of both plants receives two pieces. However, a single piece is already enough to keep a house safe.

A house outside every high-risk zone belongs to the low-risk zone and initially receives no equipment. A house holding two pieces may give its spare to a low-risk house, so that the low-risk house also has one piece. Even after this redistribution, some houses may still end up with no equipment.

Given the positions of the houses, the positions of the two plants, and several possible $R_1, R_2$ pairs, write a program that, for each pair, computes the number of houses that end up without protective equipment.

The input consists of at most 3 test cases. Each test case has the following format.

• The first line contains the number of houses $N$. ($0 < N \le 200000$)
• The next $N$ lines each contain the coordinates $x_i, y_i$ of a house. ($0 \le x_i, y_i \le 20000$) No two houses share the same location.
• The next line contains $a_x, a_y, b_x, b_y, q$. ($0 \le a_x, a_y, b_x, b_y \le 20000$, $0 < q \le 20000$) $(a_x, a_y)$ and $(b_x, b_y)$ are the coordinates of the two plants, and $q$ is the number of $R_1, R_2$ pairs to check.
• The next $q$ lines each contain $R_1, R_2$. ($0 < R_1, R_2 \le 13000$)

After all test cases, a final line contains a single $0$.

For each test case, print $q+1$ lines. The first line prints the test case number in the form Case k: ($k$ starts from 1). The following $q$ lines print, in the input order of the $R_1, R_2$ pairs, the number of houses that end up without protective equipment.