Problem Description

Mirko and Slavko are playing a game on an \( R \times C \) chessboard. Each places a certain number of kings on the board—a king can move one step in any of the 8 possible directions. The rules are as follows:

• The "distance" between two kings is defined as the minimum number of steps required for one king to reach the square occupied by the other king.
• The "expansion" of a player is the sum of the distances between all pairs of kings belonging to that player.

Calculate the "expansion" for both Mirko and Slavko.

Input Format

The first line contains two integers \( R \) and \( C \).

The next \( R \) lines contain \( C \) characters each, where 'M' represents a king placed by Mirko, 'S' represents a king placed by Slavko, and '.' represents an empty square. It is guaranteed that each player has at least one king on the board.

Output Format

Output two integers, representing the "expansion" of Mirko and Slavko respectively.

Sample Input and Output

Sample Input #1

2 3
SMS
MMS

Sample Output #1

3 5

Sample Input #2

2 3
S.M
M..

Sample Output #2

2 0

Sample Input #3

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

Sample Output #3

10 13

Notes/Hints

• For 20% of the test cases, the total number of kings on the board does not exceed 5000.
• For 60% of the test cases, \( R, C \leq 300 \).
• For 100% of the test cases, \( 1 \leq R, C \leq 1000 \).

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

The score for this problem is set according to the original COCI contest, with a maximum of 120 points.

见题面 Input 部分

见题面 Output 部分