FiFo | RoAlgo Educational Contest #1 | artclass

Cosmin was bored (again) in art class, when the teacher told him that he could draw anything he wanted, just to do something. At that moment, Cosmin realized that the only thing he could draw was a line. So he started to draw different shapes on a sheet of paper representing a table, using only one unit long lines, parallel to the contour of the sheet he was drawing on. He would start with one line, and then continue with new lines, each one having a point in common with the last one, thus ensuring the continuity of the shape.

Task

Three numbers, $N$, $M$ and $Q$, are given, representing the height and width of the sheet Cosmin draws, measured in units, and the number of shapes he draws, followed by their description. What is the maximum value of the area of any rectangular surface that fits on the sheet, outside all the shapes?

Input data

The first line will contain the natural numbers $N$, $M$ and $Q$. On the following $2 * Q$ lines the $Q$ shapes are described, so that for each of them: the first line contains two natural numbers, representing the coordinates of the starting point on the drawing sheet, i.e. the line and the column, and the second line a string of characters, each character representing the direction in which the current line is drawn, relative to the last point drawn (N for north, S for south, E for east and V for west). Numbers on the same line are separated by a space.

Output data

A single number will be displayed representing the maximum value of the area of any rectangular surface that fits on the sheet, outside all shapes.

Constraints and clarifications

• $3 \leq N, M \leq 1 \ 000$;
• It is guaranteed that, within a shape, the last point drawn coincides with the first point drawn;
• Any point is guaranteed to be drawn at most once;
• A shape is guaranteed not to contain another shape inside it;
• It is guaranteed that no lines are drawn on the outline of the drawing sheet;
• The first line of a shape has its origin in the bottom right corner of the starting cell;

Comment

Due to the very large input data, we recommend using the following lines at the beginning of the main() function in the C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example

stdin

6 9 3
4 2
ESVN
2 7
SSVVVSEEEENNNNVVVVSEEE
1 1
ESVN

stdout

14

Explanation

The shapes are outlined in red.
The maximum area is highlighted in blue.