21664_ACarnivalGame

Maybe you have ever played such a kind of carnival game (If not, you can go to Tee Mall or Grandview Mall to have a try A_A):

There are a lot of semicircles on the desk. Every semicircle is divided into several parts. You can throw a coin to the desk. If your coin lies in some part without intersecting any arcs or lines, you can get the corresponding prize, e.g., a small prize, middle prize, big prize or even gold prize, as shown in Figure 1 (a).

This problem is base on this game. To make things complicated, you have to deal with sectors instead of semicircles. There are N sectors on the desk. The sectors will not overlap. Every sector is divided into K parts. You can assume that the sector is cut from a group of concentric circles whose radius form an arithmetic progression (a list of numbers A_i satisfying that A_i - A_i-1 = d for all i > 1). Initially, the whole desk is white. Then each part of every sector is colored differently. Figure 1 (b) shows an example of a sector when K = 5.

You can throw some coins to the desk. A coin is a circle. If your coin lie in the colored part inside a sector and doesn't intersect any arc or segment of any sector, you can get some score. From the outer part to the inner part, the score you can get is 1, 2, 3, ..., K separately. Otherwise, the score is 0.

Now, given the description of the N sectors and the Q coins, I'd like you to tell me the score every coin can get.

Note: A coin intersects an arc or a segment if and only if their minimum distance is less than 1E-6.

There are multiple test cases in this problem.

The first line contains an integer T ( 1 ≤ T ≤ 10 ) indicating the number of test cases.

For each test case, the first line contains two positive integers N and K ( 1 ≤ N ≤ 5000, 1 ≤ K ≤ 5000 ), indicating the number of sectors and the number of parts.

Then N lines followed, each line contains five floating number x₁, y₁, x₂, y₂, r ( -1000000 < x₁, y₁, x₂, y₂ < 1000000,  0 < r < 1000000 ). It means that there is a sector whose arc is (x₁, y₁)-(x₂, y₂) (in counter-clockwise order) and radius is r. The angle of the sector will never be more than 180 degrees.

After that, there is a line containing one integer Q ( 1 ≤ Q ≤ 20 ), indicating the number of coins. Then Q lines followed, each line contains three floating number x, y, r ( -1000000 < x, y < 1000000,  0 < r < 1000000 ). It means there is a coin whose center is (x, y) and radius is r.

For each test case, first print the case number (start from 1) in the format of "Case i:" in a line, as shown in the sample output.

Then print Q lines, each line contains an integer indicating the score of the corresponding coin.

2
1 2
1 0 0 1 1
2
0.5 0.5 0.2
0.5 0.5 0.5
2 2
0.6 0 0 0.6 0.6
1.7 1 0.7 0 1
4
0.1 0.1 0.05
0.1 0.1 0.1
0.67 0 0.05
0.9 0.15 0.1

Case 1:
1
0
Case 2:
2
0
0
1