Internet Problem Solving Contest

IPSC 2004

Problem F – Fat Rat

Johnny the Rat lives in the sewer system. He enjoys walking through the pipes. Johnny is quite fat; actually it is almost impossible to distinguish him from a sphere, yet he used to be able to pass through all the pipes comfortably.

Unfortunately, things have changed now. With the expansion of the Internet, some providers place their cables even in the sewer pipes! Johnny is worried that he may get stuck in one of his favourite pipes. Please help him to determine through which pipes he can still pass.

Input Specification

The first line of the input file contains two numbers: J – diameter of Johnny the Rat and P – the number of Johnny's favourite pipes. The specification of the P pipes follows.

Description of each pipes starts with a line containing two numbers: D – diameter of the pipe and N – the number of cables crossing the pipe. The shape of the pipe is a cylinder of an infinite height, with diameter D, and its axis coincides with the z-axis of the coordinate system. Each of the next N lines contains 7 real numbers (x1, y1, z1, x2, y2, z2, d) specifying one cable. Shape of a cable is a cylinder of an infinite height, with axis [x1,y1,z1][x2,y2,z2], and with diameter d.

Output specification

Output file should contain one line for each pipe with a single word "YES", if it is possible for Johnny to walk through the pipe without crossing the cables, or "NO" otherwise.


3 2
7 1
-2 0 0 -2 1 0 1.5
7 2
-2 0 0 -2 1 0 1.5
2 0 0 2 1 0 1.5