24992번 - Joining Pairs 다국어

Alexander and Melina are really good friends. After a long summer of playing games together, they finally had to take the bus back home. Since they had such an active summer, they were getting bored from the bus ride, so Alexander challenged Melina to one final puzzle.

Alexander gave Melina a piece of graph paper W centimeters wide and H centimeters tall. The paper was subdivided into 1 × 1 squares, forming a W × H coordinate system. In the paper, Alexander had drawn many colorful points, in such a way that there were exactly two points of each color, all points were at integer coordinates (possibly including the edges and corners of the paper) and there were no two points in the same spot.

Alexander asked Melina to draw a line between each pair of equally colored points, connecting them. The lines connecting the points couldn’t touch each other. However, they could assume an arbitrary shape (as long as they remained inside the paper) and they could be considered infinitely thin.

Melina argued with Alexander that the game was unfair since there was no way to satisfy his requirements. Alexander assured her that the game was fair, and she simply had to “get good” to solve the challenge. After much arguing, the friends decided to task you, an unbiased observer, with determining whether the game is fair or not.

In the example above, Melina can connect each pair of points without crossing lines, therefore the game is fair. On the contrary, in the example below, Melina can’t connect the twos without crossing whichever line connects the ones, therefore the game is not fair.

The first line contains two integers W and H (1 ≤ W, H ≤ 10⁹), indicating respectively the width and height of the paper. The second line contains an integer N (1 ≤ N ≤ 10⁵), representing the number of pairs of points drawn in the paper. Each of the next N lines contains four integers X₁, Y₁, X₂ and Y₂ (0 ≤ X₁, X₂ ≤ W and 0 ≤ Y₁, Y₂ ≤ H), representing a pair of points of the same color drawn at coordinates (X₁, Y₁) and (X₂, Y₂). No two points have the same location.

Output a single line with the uppercase letter “Y” if the game is fair, and the uppercase letter “N” otherwise.