Don't Cross the Circles!

Time limit1sMemory limit256 MB

Summary

Decide whether two points can be joined by a curve that crosses none of up to 100 given circle circumferences.

Level: Medium6 of 10
Topics: Graph, Geometry, BFS
Solved: No attempts yet

Problem

One or more circles lie on a plane. Any two circles differ in center position, in radius, or in both. A circle may overlap another circle, but no three or more circles share an area or a point. A circle may contain another circle completely, and two circles may meet at two distinct points, but the circumferences of two circles never touch at a single point.

Given two points $P$ and $Q$ , decide whether a path connects them without crossing the circumference of any circle. The path may be any curve as long as it stays off every circumference. Each layout of circles comes with one or more point pairs.

Input

The input has several datasets, each in the following format.

$n$ $m$

$Cx_1$ $Cy_1$ $r_1$

...

$Cx_n$ $Cy_n$ $r_n$

$Px_1$ $Py_1$ $Qx_1$ $Qy_1$

...

$Px_m$ $Py_m$ $Qx_m$ $Qy_m$

The first line of a dataset has two integers $n$ and $m$ separated by a space. $n$ is the number of circles and satisfies $1 \le n \le 100$ . $m$ is the number of point pairs and satisfies $1 \le m \le 10$ . Each of the next $n$ lines has three integers separated by a space. $(Cx_i, Cy_i)$ is the center of the $i$ -th circle and $r_i$ is its radius. Each of the next $m$ lines has four integers separated by a space. They give the coordinates of two points $P_j = (Px_j, Py_j)$ and $Q_j = (Qx_j, Qy_j)$ , which form the $j$ -th point pair. The coordinates and the radii satisfy $0 \le Cx_i \le 10000$ , $0 \le Cy_i \le 10000$ , $1 \le r_i \le 1000$ , $0 \le Px_j \le 10000$ , $0 \le Py_j \le 10000$ , $0 \le Qx_j \le 10000$ , $0 \le Qy_j \le 10000$ . $P_j$ and $Q_j$ are two different points, and neither lies on the circumference of any circle.

The end of the input is a line with two zeros separated by a space.

Output

For each dataset, print the $m$ results on one line, separated by single spaces. The $j$ -th result is YES if a path connects $P_j$ and $Q_j$ , and NO otherwise.

Examples1

Example 1

Input

5 3
0 0 1000
1399 1331 931
0 1331 500
1398 0 400
2000 360 340
450 950 1600 380
450 950 1399 1331
450 950 450 2000
1 2
50 50 50
0 10 100 90
0 10 50 50
2 2
50 50 50
100 50 50
40 50 110 50
40 50 0 0
4 1
25 100 26
75 100 26
50 40 40
50 160 40
50 81 50 119
6 1
100 50 40
0 50 40
50 0 48
50 50 3
55 55 4
55 105 48
50 55 55 50
20 6
270 180 50
360 170 50
0 0 50
10 0 10
0 90 50
0 180 50
90 180 50
180 180 50
205 90 50
180 0 50
65 0 20
75 30 16
90 78 36
105 30 16
115 0 20
128 48 15
128 100 15
280 0 30
330 0 30
305 65 42
0 20 10 20
0 20 10 0
50 30 133 0
50 30 133 30
90 40 305 20
90 40 240 30
16 2
0 0 50
0 90 50
0 180 50
90 180 50
180 180 50
205 90 50
180 0 50
65 0 20
115 0 20
90 0 15
280 0 30
330 0 30
305 65 42
75 40 16
90 88 36
105 40 16
128 35 250 30
90 50 305 20
0 0

Expected output

YES NO NO
YES NO
NO NO
NO
YES
YES NO NO YES NO NO
NO NO