Sara's cat Utopia has gone missing. It's dark and Sara's worried, so she gathers a bunch of her friends to look for Utopia. Each member of the search party stands somewhere in an open field, facing and pointing a flashlight in one of the cardinal directions (north, east, south, or west). The flashlight illuminates anything in front of the holder, up to 45 degrees (inclusive) to the left or right of the direction the person is facing.
Given the position of Utopia, and the name, position, and direction faced by each person in the search party, your program will print a list of the people who can see Utopia in their own flashlight beam.
Input: The first line contains two decimal integers (separated by a space) indicating the coordinates (in metres east and north of the middle of the field) of Utopia.
Each line in the rest of the input gives information about one person in the search party. Each of the four fields is separated by spaces. The fields are: person's name (an alphabetic string), their x coordinate (number of metres east of the middle of the field), their y coordinate (number of metres north of the middle of the field), and the direction they face (N for north, i.e. increasing y, E for east, i.e. increasing x, S for south, i.e. decreasing y, W for west, i.e. decreasing x).
Each coordinate is a decimal integer with absolute value at most 10000. Each name is at most 20 letters long.
Output: Output the names of the members of the search party who see Utopia in their own flashlight beam. (Flashlights are powerful: their beams never fade with distance.) A person standing at the same location as Utopia sees Utopia. A person can see through people. The names should be in the same relative order as in the input. Each name should appear on a line by itself, and each line should be terminated with a newline character.
4 5 Sara 3 3 N Mary 2 5 N Jane 4 5 E Toby 5 6 S Rebecca 6 7 W Jasmine 4 3 SCorresponding sample output:
Sara Jane Toby Rebecca