Misha is engaged in parallel programming. Today he is writing a program for the performer "Kvadratik". Performer "Kvadratik" lives on a checkered field of size N x M, the size of one cell is 1x1. As he moves, he paints over the cell he has visited. The cell on which he started moving and on which he stopped is also painted over.
Misha installed on the field K "Kvadratikov". Each "Square" will move in the direction indicated by Misha and stop when he reaches the end of the field. After the movement of all "Squares" is over, Misha wants to know how many cells of the field turned out to be painted over. Since the task of counting is not related to parallel programming, and the size of the field can be very large, Misha asked you to write a program to count such cells.
Input
The program takes several lines as input. The first line contains integers M and N - sizes of the "Square" artist field (1 <= M, N <= 106). The second line contains the number K - the number of "Squares" on the field (0 <= K <= 103). Then there are K lines, each of which describes the position of a certain "Square" and the direction in which it will move. The format of each of these strings is: two integers separated by one space and one character {N, E, S< /code>, W} - initial coordinates and direction of movement of the corresponding "Square". A character is separated from numbers by exactly one space.
The following directions of movement N - up, S - down, W - left, E< /code> - right.
Output
Output the number of filled squares of the field, after the end of the movement of all "Squares".
Explanations
The field of the performer and the location of the "Squares" for the first example are shown in the figure below. The arrow indicates the direction of movement of the corresponding "Square".
Examples
| # |
Input |
Output |
| 1 |
8 5
4
4 4S
6 2W
6 3 N
6 4S
|
13
|