Dominance

Time limit2sMemory limit128 MB

Summary

Given up to 3000 colored squares each with a Manhattan-distance attack range on a huge grid, count how many grid cells are dominated by white versus black using a diamond-shaped coverage counting technique.

Level: Hard8 of 10
Topics: Geometry, Prefix sum, Sorting
Solved: No attempts yet

Problem

Bugtopia is a grid of $W \times H$ unit squares, inhabited by white bugs and black bugs. Every square is one of three kinds: a white square (inhabited only by white bugs), a black square (inhabited only by black bugs), or an empty square (uninhabited).

White bugs and black bugs are hostile to each other, and each color wants to dominate Bugtopia. To do so the bugs move across the grid, where a move to a horizontally or vertically adjacent square counts as one step. The bugs living on a square can attack another square if they can reach it in at most a certain number of steps. This range depends on the square the bugs come from, because different squares offer different living conditions.

A square is dominated by the white bugs if it can be attacked from strictly more white squares than black squares. Likewise, a square is dominated by the black bugs if it can be attacked from strictly more black squares than white squares. A square is neutral if it can be attacked from no square, or from equally many white and black squares; a neutral square is dominated by neither color.

Bugtopia example

In the picture above there are two white squares (white circles) with ranges 3 and 2, and one black square (black circle) with range 2. The white bugs dominate 30 squares and the black bugs dominate 9 squares. The three light-gray squares can be attacked but are neutral, so they are dominated by neither color.

Given the grid size and the position, color, and range of every inhabited square, output how many squares are dominated by each color.

Input

The first line contains two integers $W$ and $H$ , the width and height of the grid ( $1 \le W, H \le 10^9$ ).

The second line contains one integer $N$ , the number of inhabited squares ( $0 \le N \le 3000$ ).

Each of the next $N$ lines describes one inhabited square as a character $c_i$ and three integers $x_i$ , $y_i$ , $r_i$ separated by single spaces: the color, the coordinates, and the range of the square. The color $c_i$ is either W (white) or B (black), and $0 \le x_i < W$ , $0 \le y_i < H$ , $0 \le r_i < 5 \cdot 10^8$ . The bottom-left square of the grid has coordinates $(0, 0)$ and the top-right square has coordinates $(W-1, H-1)$ . No square's range ever reaches beyond the borders of the grid.

Output

Output a single line with two integers separated by one space: the number of squares dominated by the white bugs, followed by the number of squares dominated by the black bugs.

Examples6

Example 1
Input
```
10 10
3
W 3 6 3
B 6 4 2
W 3 3 2
```
Expected output
```
30 9
```
Example 2
Input
```
1 1
0
```
Expected output
```
0 0
```
Example 3
Input
```
5 5
1
W 2 2 0
```
Expected output
```
1 0
```
Example 4
Input
```
11 11
1
B 5 5 2
```
Expected output
```
0 13
```
Example 5
Input
```
12 12
2
W 5 5 2
B 5 5 2
```
Expected output
```
0 0
```
Example 6
Input
```
15 15
3
W 5 5 3
W 9 5 3
B 7 5 2
```
Expected output
```
39 2
```