C :: Cutting a Cake

Time Limit: 2 Seconds    Memory Limit: 65536 KB

We have a large cake of size 100 × 100 × 1 cm. The surface of the cake can be viewed as a 100 × 100 grid, with each grid box being 1 × 1 cm. We want to cut the cake into pieces using a knife, initially located at a vertex of the grid. We are restricted to move the knife only along the edges of the grid, without lifting up the knife at any step. After finishing the cut, we can pick only those pieces of the cake which are cut completely from all sides. In other words, if the trajectory of the knife is given as a rectilinear curve along the grid edges, we can pick only those pieces which are enclosed by the trajectory curve. Note that if a piece has a side on the grid boundary, the piece can picked provided that all its sides even its side on the grid boundary are cut by the knife. We want to compute the amount of cake we can pick if the trajectory of the knife on the cake is given.

Input

There are multiple test cases in the input. The first line of each test case contains three integers x, y and  n , where (x,  y) denotes the starting point of the knife on the grid, and n is the number of knife moves. (x,  y, and n are all non-negative integers,  x is the distance in centimeters from the left edge of the cake, y is the distance in centimeters from the bottom edge of the cake.  x, y and n range from 0 to 100, inclusive.)
The next n lines will contain a character d and an integer i , separated by a space. The character d is from the set {‘L’, ‘R’, ‘U’, ‘D’}, indicating the left, right, up, and down directions, respectively, and the integer i indicates how far in that direction the knife is moved.
You can assume that the knife trajectory will never leave the 100 × 100-surface of the cake. The trajectory may or may not be closed. It may cross itself, or may trace an edge several times even boundary edges. The input terminates with a line containing 0 0 0.

Output

For each data set, output a single line containing the volume of cake in cubic centimeters that can be picked after the cut (i.e., enclosed by the knife trajectory).

Sample Input

10 10 8
U 20
R 50
U 20
L 30
D 40
R 20
U 30
R 20
0 0 8
U 25
R 25
U 25
R 25
D 25
L 25
D 25
L 25
0 0 0

Sample Output

1000
1250

Submit

Source: 10th Iran Nationwide Internet Contest