The Shields

Time Limit: 18000/9000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

General Zhang recently got a plasma shield to intercept incoming missiles.

The shape of the plasma shield is basically a square with a horizontal diagonal. Due to some technology issues, the plasma shield cannot protect the whole square area. One vertical stripe in the middle of the square is penetrable to the missiles. So, in fact the shield is formed by two identical isosceles right triangle. Missiles hitting the surface or the edge of the shield are considered intercepted.



Now $N$ missiles are coming to General Zhang’s army. The $i-th$ missile will strike the position $(x_i,y_i)$. Because he only has one plasma shield, he want to calculate when the shield is turned on in a particular way, how many of the missiles it can stop.

General Zhang will give you $M$ queries, each query describe the shape of a plasma by 4 integers $(X,Y,D,W)$. $(X,Y)$ denotes the center of the shield. $D$ denotes the length of the diagonal. $W$ denotes the width of the unprotected stripe. For each query, you need to output number of the missiles stopped by the shield.

Input

The first line of input contains an integer $T$ ($T≤20$), which represents the number of test cases.
Each test case starts with $N$ and $M$ ($1≤N,M≤20000$) in a line. The $i-th$ line of the next $N$ lines contains two integers $x_i$ and $y_i$. The next $M$ lines each line has 4 integers $X,Y,D,W$, which represents a query. $D$ and $W$ are guaranteed to be even numbers.

Output

For each test case, output a single line consisting of “Case #X:” first. $X$ is the test case number starting from 1. For each query, output the number of missiles that are intercepted in a single line. Do not output extra spaces or newlines.

Sample Input

1 4 3 -5 0 -4 0 -3 0 0 0 0 0 0 0 0 0 8 0 0 0 8 2

Sample Output

Case #1: 1 3 2

Hint

wange2014

Source

2015ACM/ICPC亚洲区合肥站-重现赛(感谢中科大)

提交代码