Problem Description

Mirko and Slavko are playing a game on an $R \times C$ chessboard. Each of them places some kings on the board. A king can move $1$ step each move in any of the $8$ directions. The rules are:

• The “distance” between two kings is the minimum number of moves needed for one king to move to the square of the other king.
• A player’s “spread” is the sum of distances over all pairs of that player’s kings.

Compute the “spread” for Mirko and for Slavko.

Input Format

The first line contains two integers $R, C$.

The next $R$ lines each contain $C$ characters $\texttt M$ / $\texttt S$ / $\texttt .$ , representing Mirko’s kings, Slavko’s kings, and empty squares. The testdata guarantees that each side has at least one king on the board.

Output Format

Output two integers, representing the “spread” of Mirko and the “spread” of Slavko, respectively.

2 3
SMS
MMS

3 5

2 3
S.M
M..

2 0

4 5
M....
..S.M
SS..S
.M...

10 13

Hint

Constraints

• For $20\%$ of the testdata, the total number of kings on the board does not exceed $5000$.
• For $60\%$ of the testdata, $R, C \le 300$.
• For $100\%$ of the testdata, $1 \le R, C \le 1000$.

Hints and Notes

This problem is translated from COCI 2009-2010 CONTEST #7 Task 5 KRALJEVI.

The score of this problem follows the original COCI setting, with a full score of $120$.

Translated by ChatGPT 5