지배

시간 제한2초메모리 제한128 MB

요약

최대 3000개의 색칠된 사각형과 각 사각형의 맨해튼 거리 공격 범위가 주어질 때, 거대한 격자에서 흰색과 검은색 중 어느 쪽이 더 많이 도달하는 칸의 수를 계산합니다.

난이도: 어려움10점 중 8점
유형: 기하, 누적 합, 정렬
정답자: 아직 제출이 없습니다

문제

버그토피아(Bugtopia)는 가로 $W$ 칸, 세로 $H$ 칸으로 이루어진 격자 땅이며, 흰색 벌레와 검은색 벌레가 산다. 모든 칸은 다음 세 종류 중 하나이다: 흰색 벌레만 사는 흰색 칸, 검은색 벌레만 사는 검은색 칸, 아무도 살지 않는 빈 칸.

흰색 벌레와 검은색 벌레는 서로 적대적이며, 각 색깔은 버그토피아를 지배하려고 한다. 이를 위해 벌레들은 격자 위를 이동하는데, 상하좌우로 인접한 칸으로 한 번 움직이는 것을 한 걸음으로 센다. 어떤 칸에 사는 벌레들은 정해진 걸음 수 이내로 도달할 수 있는 다른 칸을 공격할 수 있다. 이 사거리는 벌레가 출발하는 칸마다 다른데, 칸마다 사는 환경이 다르기 때문이다.

어떤 칸이 검은색 칸보다 더 많은 흰색 칸에서 공격받을 수 있으면, 그 칸은 흰색 벌레에게 지배당한다고 한다. 마찬가지로 흰색 칸보다 더 많은 검은색 칸에서 공격받을 수 있으면 그 칸은 검은색 벌레에게 지배당한다. 어떤 칸에서도 공격받을 수 없거나, 흰색 칸과 검은색 칸에서 똑같은 수만큼 공격받을 수 있는 칸은 중립이며, 어느 색에게도 지배당하지 않는다.

버그토피아 예시

위 그림에는 사거리가 각각 3과 2인 흰색 칸 두 개(흰 동그라미)와 사거리가 2인 검은색 칸 하나(검은 동그라미)가 있다. 흰색 벌레는 30칸을, 검은색 벌레는 9칸을 지배한다. 연한 회색으로 칠해진 세 칸은 공격받을 수는 있지만 중립이어서 어느 색에게도 지배당하지 않는다.

격자의 크기와 각 벌레 칸의 위치, 색깔, 사거리가 주어질 때, 각 색깔이 지배하는 칸의 개수를 출력하여라.

입력

첫째 줄에 격자의 가로와 세로 크기를 나타내는 두 정수 $W$ 와 $H$ 가 주어진다 ( $1 \le W, H \le 10^9$ ).

둘째 줄에 벌레가 사는 칸의 개수 $N$ 이 주어진다 ( $0 \le N \le 3000$ ).

다음 $N$ 개의 줄에는 각각 벌레가 사는 칸 하나가 문자 $c_i$ 와 세 정수 $x_i$ , $y_i$ , $r_i$ 로 주어지며, 각 값은 공백 하나로 구분된다. 이는 각각 칸의 색깔, 좌표, 사거리를 뜻한다. 색깔 $c_i$ 는 W(흰색) 또는 B(검은색)이고, $0 \le x_i < W$ , $0 \le y_i < H$ , $0 \le r_i < 5 \cdot 10^8$ 이다. 격자의 왼쪽 아래 칸의 좌표는 $(0, 0)$ 이고 오른쪽 위 칸의 좌표는 $(W-1, H-1)$ 이다. 어떤 칸의 사거리도 격자의 경계를 벗어나지 않는다.

출력

한 줄에 두 정수를 공백 하나로 구분하여 출력한다. 흰색 벌레가 지배하는 칸의 개수를 먼저 출력하고, 이어서 검은색 벌레가 지배하는 칸의 개수를 출력한다.

예제6

예제 1
입력
```
10 10
3
W 3 6 3
B 6 4 2
W 3 3 2
```
예상 출력
```
30 9
```
예제 2
입력
```
1 1
0
```
예상 출력
```
0 0
```
예제 3
입력
```
5 5
1
W 2 2 0
```
예상 출력
```
1 0
```
예제 4
입력
```
11 11
1
B 5 5 2
```
예상 출력
```
0 13
```
예제 5
입력
```
12 12
2
W 5 5 2
B 5 5 2
```
예상 출력
```
0 0
```
예제 6
입력
```
15 15
3
W 5 5 3
W 9 5 3
B 7 5 2
```
예상 출력
```
39 2
```