Draw a Mess

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

It's graduated season, every students should leave something on the wall, so....they draw a lot of geometry shape with different color.

When teacher come to see what happened, without getting angry, he was surprised by the talented achievement made by students. He found the wall full of color have a post-modern style so he want to have an in-depth research on it.

To simplify the problem, we divide the wall into n*m (1 ≤ n, m ≤ 10000) pixels, and we have got the order of coming students who drawing on the wall. We found that all students draw four kinds of geometry shapes in total that is Diamond, Circle, Rectangle and Triangle. Because the students just want to draw a mess, so many shape overlap with each other.

Initially all pixels is white, once a pixel is drawing by someone it will turned to black.

There are q (1 ≤ q ≤ 100) students who have make a drawing one by one. And after q operation we want to know the amount of black pixels on the wall.

Input

There are multiple test cases.

In the first line of each test case contains three integers n, m, q.

The next q lines each line contains a string at first indicating the geometry shape:

  • Circle: given xc, yc, r, and you should cover the pixels(x, y) which satisfied inequality (x - xc)2 + (y - yc)2 ≤ r2
  • Diamond: given xc, yc, r, and you should cover the pixels(x, y) which satisfied inequality abs(x - xc) + abs(y - yc) ≤ r
  • Rectangle: given xc, yc, l, w, and you should cover the pixels(x, y) which satisfied xc ≤ x ≤ xc+l-1, yc ≤ y ≤ yc+w-1
  • Triangle: given xc, yc, w, w is the bottom length and is odd, the pixel(xc, yc) is the middle of the bottom. We define this triangle is isosceles and the height of this triangle is (w+1)/2, you should cover the correspond pixels; 

Note: all shape should not draw out of the n*m wall! You can get more details from the sample and hint. (0 ≤ xc, x ≤ n-1, 0 ≤ yc, y ≤ m-1)

Output

For each test, please output an integer on a single line indicating the answer of the problem.

Sample Input

8 8 4
Diamond 3 3 1
Triangle 4 4 3
Rectangle 1 1 2 2
Circle 6 6 2

Sample Output

23

Hint

The final distribution of the wall:
00000000
03300000
03310000
00111000
00022240
00002444
00004444
00000444

Source

dut200901102

Manager

Information
Solved Number2
Submit Number17
Problem Tags
implementation
sortings
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel