Ice Fractures and Igloos

A remote fishing village built on the surface of a frozen arctic lake is in danger as global warming causes ice fractures. The village consists of n igloos, each modeled as a circle on the coordinate plane. The center of an igloo is an integer coordinate and its radius is a positive floating‐point number less than 1 with exactly one fractional digit.

You are given the locations of possible ice fractures as q queries. Each query is a straight line segment defined by its two endpoints. A segment is said to intersect an igloo if it shares at least one point with the interior of the igloo (i.e. the point lies strictly inside the circle, not just on its boundary).

For a circle with center \( P=(P_x,P_y) \) and radius \( r \), and a segment from \( A=(x_1,y_1) \) to \( B=(x_2,y_2) \), the test is as follows:

Compute the parameter \( t=\max(0, \min(1, \frac{(P-A)\cdot(B-A)}{\|B-A\|^2})) \) and let \( Q=A+t(B-A) \) be the projection of \( P \) on the line through \( A \) and \( B \). Then, with \( d=\sqrt{(P_x-Q_x)^2+(P_y-Q_y)^2} \), the segment intersects the igloo if \( d < r \).

inputFormat

The input is given as follows:

n q
x y r       (for each of the n igloos)
x1 y1 x2 y2 (for each of the q queries)

Where:

• n is the number of igloos.
• q is the number of queries.
• For each igloo, x and y are integers, and r is a floating-point number with one digit after the decimal point (and \( r<1 \)).
• Each query consists of four numbers representing the coordinates of the two endpoints of a segment.

outputFormat

For each query, output a single integer on a separate line indicating the number of igloos that intersect with the interior of the given segment.

sample

1 1
0 0 0.5
-1 0 1 0

1