1424 - Circles and Points

Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.