Description

Little Bernie loves to look at the stars in the sky. His favorite constellation is the Ball of Paper Constellation, because of its distinct and unmistakable shape of. . . a ball of crumpled paper. Bernie downloaded a picture of the constellation from the internet, and now he wants to print it and stick it to his wall. Bernie also likes to watch the paper sheets gradually coming out of the printer, and for this occasion, he made a decision: he wants the stars to be printed in non-increasing order of brightness.

The constellation has \$N\$ stars. For each one, Bernie knows its brightness level \$B\$ as well as its \$X\$ and \$Y\$ coordinates in the picture, where the \$X\$ direction points rightwards and the \$Y\$ direction points upwards. He knows that the pictures are printed from top to bottom (that is, in decreasing order of the \$Y\$ coordinate), and that everything in a horizontal line is printed simultaneously.

Bernie's plan can be described like this: for any two stars \$S\$ and \$T\$, if \$S\$ is brighter than \$T\$, then \$S\$ must be printed before or at the same time as \$T\$. Before printing the picture, Bernie can rotate it at any angle around any given point, but he cannot scale, reflect or distort it. Now Bernie needs your help to  find out if there is any rotation that allows the stars to be printed in the order he wants.

Input

The  first line contains an integer \$N (3 \leq N \leq 1000)\$ indicating the number of stars in the constellation. Each of the next \$N\$ lines describes a star with three integers \$X, Y (-10^4 \leq X, Y \leq 10^4)\$ and \$B (1 \leq B \leq 1000)\$, where \$X\$ and \$Y\$ are the coordinates of the star in the picture, and \$B\$ is its brightness level. No two stars have the same location

Output

Output a single line with the uppercase letter "Y" if there is any rotation that allows the stars to be printed in non-increasing order of brightness, and the uppercase letter "N" otherwise.

Samples

Input Copy
4
0 2 1
1 -1 2
3 3 5
4 0 2
Output
Y
Input Copy
5
0 4 6
2 4 5
3 7 2
4 4 6
3 0 8
Output
Y
Input Copy
4
-1 2 5
0 0 2
3 4 1
4 2 4
Output
N

Source

ICPC Latin American Regional - 2019
Problem Information

 Time Limit: 1000MS (C/C++,Others×2) Memory Limit: 256MB (C/C++,Others×2) Special Judge: No AC/Submit: 1 / 1 Tags:
Contests involved

 1039. ICPC Latin American Regional 2019