Counting the Ghostly Spines

In a 2D plane, there are (n) spines, each with a unique position and one of four possible orientations: right, left, up, or down. A special ordered triple of spines ((s_1, s_2, s_3)) is called a "ghostly spine" if it meets the following conditions:

1. (s_1) faces right, (s_2) faces left, and (s_3) faces up.
2. (x(s_1) < x(s_2) \leq x(s_3)), where (x(s)) denotes the x-coordinate of spine (s).
3. (y(s_2) > y(s_1) > y(s_3)), where (y(s)) denotes the y-coordinate of spine (s).
4. (x(s_2) - x(s_1) \leq d), where (d) is a given constant representing kid's width.

The coordinate system is set up so that the positive (x)-axis points from left to right and the positive (y)-axis points from bottom to top.

Given the positions and orientations of the spines, count how many ghostly spines there are. Note that spines facing down are irrelevant in forming a ghostly spine.

inputFormat

The first line contains two integers (n) and (d) (the number of spines and the constant width, respectively). The following (n) lines each contain two integers and a character, representing the (x) coordinate, the (y) coordinate, and the orientation of a spine. The orientation is given as one of the characters R (right), L (left), U (up), or D (down). All spines have distinct positions.

outputFormat

Output a single integer: the number of ghostly spines as defined.

sample

3 5
1 3 R
3 5 L
4 1 U

1