Wall Clocks

You manage a chocolate sales team. The team takes a tea break every two hours and tastes the new chocolate products of the company at each break. Everyone looks forward to the break, so they glance at a wall clock often.

The team moved to a new office recently, and you have just finished arranging the desks. One member asked you to hang a clock on the wall in front of her desk so that she is not late for a break, and everyone else agreed with her.

You decided to hang enough clocks that every member has one in view. A member is satisfied if at least one clock is within 45 degrees to the left and 45 degrees to the right (both ends included) of the direction the seat faces. The orientation of the clock itself does not matter. You want to buy as few clocks as possible, so compute the minimum number of clocks that satisfies everyone.

The office is a rectangle whose sides run east to west and north to south. The walls are tall enough that you can hang a clock above the door, and neither other members nor furniture block anyone's line of sight. A clock is a point of size zero, so you can hang one even at a corner of the room.

Figure 1. Arrangements of seats and clocks. The gray area is the field of view.

For example, suppose the team has two members. If they sit facing each other as in Figure 1(A), the wall sections they see are disjoint, so you need two clocks. In the arrangement of Figure 1(B) their fields of view meet at a single point on the wall, so one clock hung at that point is enough. In Figure 1(C) the two fields of view share a section of the wall, and one clock anywhere in that section is enough. Arrangements (A), (B), and (C) in Figure 1 correspond to the first, the second, and the third example.

The input consists of a single test case in the following format.

n w d
x1 y1 f1
...
xn yn fn

Every value in the input is an integer. The first line contains the number of team members $n$ ($1 \le n \le 1000$) and the size of the office $w$ and $d$ ($2 \le w, d \le 100000$). The office has width $w$ east to west and depth $d$ north to south. Each of the following $n$ lines gives the position and the orientation of one member's seat. The seat of member $i$ is at position $(x_i, y_i)$ and faces direction $f_i$, where $1 \le x_i \le w - 1$ and $1 \le y_i \le d - 1$. Each $f_i$ is one of N, E, W, and S, meaning north, east, west, and south. The position $(x, y)$ is the point at distance $x$ from the west wall and distance $y$ from the south wall. All seat positions are distinct.

Print the minimum number of clocks needed.