Guardians#2786
Petya and Vasya are back to playing spies. This time, Vasya's grandmother, acting as the adversary, has captured Vasya and taken him to a secret dacha. After several days of waiting for rescue, Vasya realized that Petya knew the location of his grandmother's dacha, which did not align with their spy game. To make the game more challenging, Vasya decided to station guards—his friends—in the forest surrounding the dacha to prevent Petya from rescuing him.
Vasya used a map of the area, set up a coordinate system with the Oy axis pointing north and the Ox axis pointing east, and marked the positions of the guards. Each guard was equipped with a powerful flashlight that illuminates a 90-degree angle in front of them. These flashlights are so strong that they can shine over any distance. However, to give Petya a fighting chance, Vasya restricted the guards to point their flashlights in only one of four directions: strictly north, west, south, or east. The bisector of the flashlight's angle aligns with the chosen direction.
To evaluate his chances of being rescued, Vasya wants to know, for each guard, how many other guards are illuminated by that guard's flashlight.
The first line of the input contains an integer (1 \leq n \leq 50000)—the number of guards in the forest. The following lines provide information about each guard. The -th line contains two integers x_i and y_i (|x_i|, |y_i| \leq 10^9)—the coordinates of the -th guard on Petya's map, followed by a letter indicating the direction the guard is facing: N, E, S, or W, representing north, east, south, and west, respectively. No two guards share the same location.
Output lines. The -th line should contain a single integer—the number of guards illuminated by the -th guard's flashlight, excluding themselves.
Example 1
Explanation of examples
First example
Second example