18722번 - Contamination 다국어

The Third World War broke out! In a short period of time there were nuclear explosions all around the world, and the explosions contaminated large areas of Earth. Radioactive contamination wiped out large populations of animals, some species became extinct, and some are now endangered.

For a number of endangered species, a pair of animals of that species was observed. We would like to know whether these two animals can safely meet. What makes the answer to that question harder is the fact that each species can only survive in a specific range of latitudes.

We model the world as a plane with standard Cartesian coordinates. The area of contamination of each of the n nuclear explosions is a circle centered at the point (c_x, c_y) with the radius r. No species can survive being at distance r or smaller from the point (c_x, c_y). The areas of contamination of the explosions are pairwise disjoint (It would be a waste to contaminate one place in the world twice!).

You are given q queries of the form (p_x, p_y, q_x, q_y, y_min, y_max), where (p_x, p_y) and (q_x, q_y) are the coordinates of two animals of the same species, and y_min and y_max define the range of latitudes in which the species can survive. You have to determine whether it is possible to get from the point (p_x, p_y) to the point (q_x, q_y), avoiding the areas of contamination and traveling only through points (x, y) with y_min ≤ y ≤ y_max. You may assume that the points (p_x, p_y) and (q_x, q_y) are not in any area of contamination.

The first line of input contains two integers n, q (1 ≤ n, q ≤ 10⁶) — the number of explosions and the number of queries.

The next n lines contain the descriptions of the explosions. Each description consists of three integers c_x, c_y, r (−10⁹ ≤ c_x, c_y ≤ 10⁹, 1 ≤ r ≤ 10⁹) — the coordinates of the center and the radius of the area contaminated by the explosion. Remember that these areas are pairwise disjoint.

The following q lines contain the queries about animals. Each query consists of six integers p_x, p_y, q_x, q_y, y_min, y_max (−10⁹ ≤ p_x, p_y, q_x, q_y, y_min, y_max ≤ 10⁹, y_min ≤ p_y, q_y ≤ y_max), with the meaning explained above.

For each query, output in a separate line “YES” if the pair of animals can safely meet, or “NO” otherwise.