1424 - Circles and Points

Time Limit: 10s Memory Limit: 128MB

Submissions: 254 Solved: 48
Description

There are m circles and n points on 2D plane, you are asked to calculate how many enclosing circles there are for each point.

A circle is an enclosing circle for point P if and only if P is strictly inside the circle (without on the boarder).

You can assume that the answer for each point is not larger than 100.

Input

The first line contains the number of test cases t. (t < 10)

For each test case:

The first line contains an integer m.(m <= 100000)

The following m lines each contains three integers: xi, yi, ri, describing the center and radius of the i-th circle.(0 < xi, yi, ri < 1000000)

The next line contains an integer n.(n <= 50000)

The following n lines each contains two integers: pxi, pyi, describing the coordinate of the i-th point.(0 < pxi, pyi < 1000000)

Output

One line contains the case info and n numbers -- number of enclosing circles for each point.

Sample Input
2
2
2 2 2
4 2 2
3
1 2
3 2
3 4
2
50000 50000 50000
50000 50000 30000
1
40000 40000
Sample Output
Case #1: 1 2 0
Case #2: 2
Hint

Source