Go

Time limit1sMemory limit128 MB

Summary

Given a sequence of legal Go stone placements on an odd n x n board, apply capture and territory rules to compute each player's final score.

Level: Medium7 of 10
Topics: Simulation, Implementation, BFS, Graph
Solved: No attempts yet

Problem

Go is played on a square board whose numbers of vertical and horizontal lines are both odd. Common sizes are 9×9, 13×13, and 19×19, but here the board is $n \times n$ for an odd $n$ with $3 \le n \le 19$ .

Black and White alternately place stones on the intersections of the lines, and Black moves first. On each turn a player may place a stone or pass; when both players pass in succession, the game ends. A placement is written $P(x, y)$ , where $P$ is B (Black) or W (White) and $\frac{1-n}{2} \le x, y \le \frac{n-1}{2}$ gives the grid position. The center intersection of the board is $(0, 0)$ .

Use the following rules:

Black plays first.
The players alternate; on each turn a player either places a stone or passes. The game ends once both players pass consecutively.
A stone may be placed only on an empty intersection.
Two intersections are connected if they are horizontally or vertically (not diagonally) adjacent. When a player P places a stone so that P's stones, together with the edge of the board, completely surround a connected group of the opponent Q's stones—that is, no stone of that group is connected to any empty intersection—every stone of that group is captured and removed from the board.
If P's placement captures Q's stones, the stone P just placed is never captured.
A connected region of empty intersections whose bordering stones are all P's (and that has no Q stone on its border) is owned by P.
Player P's score is the number of empty intersections owned by P in the final position plus the total number of Q's stones that P captured at any point during the game.

Input

The input contains several test cases. Each test case begins with a line holding two integers $n$ (the board size) and $m$ (the number of stones placed during the game). The next $m$ lines each describe one placement in the format above. Note that $m$ counts stone placements only; because of passes, the same player may place two stones in a row. Every move is guaranteed to be legal. A line containing 0 0 follows the last test case and is not processed.

Output

For each test case, print one line with two integers: Black's score followed by White's score, separated by a space.

Examples3

Example 1

Input

7 6
B(-2,-2)
W(2,2)
B(-2,-3)
W(2,3)
B(-3,-2)
W(3,2)
7 6
B(-2,-3)
W(-3,-3)
B(-2,-2)
W(3,2)
B(-3,-2)
W(2,3)
0 0

Expected output

1 1
2 1

Example 2
Input
```
3 1
B(0,0)
0 0
```
Expected output
```
8 0
```
Example 3
Input
```
3 3
B(0,1)
W(1,1)
B(1,0)
0 0
```
Expected output
```
8 0
```