Mirko and Slavko are playing a chess like game. The game is played on a non-standard chess board sized \(R\) rows by \(C\) columns. Each player starts with some number of chess kings. In chess kings can move from their current field to any of the \(8\) neighbouring fields.

Player spread is defined as the complete sum of distances between all pairs of pieces of the given player. The distance between two pieces is the smallest number of king moves required to travel from one piece to the other, i.e. \(\max(|r_1 - r_2|,\ |c_1 - c_2|)\) for pieces on fields \((r_1, c_1)\) and \((r_2, c_2)\). No actual moves are performed when calculating the distance and as such enemy pieces do not influence the result.

Mirko knows that the spread is a vital piece of strategic information and would like you to make him a program that will calculate both his and Slavko's spread.

In test cases worth 20% of total points the number of pieces on the board
will be less then or equal to 5000.
In test cases worth 60% of total points, the numbers R and C will be smaller
than or equal to 300.
SAMPLE TEST CASES
Input:
2 3
SMS
MMS
Input:
2 3
S.M
M..
Input:
4 5
M....
..S.M
SS..S
.M...
Output:
3 5
Output:
2 0
Output:
10 13

The first line of input contains two integers \(R\) and \(C\) (\(1 \le R, C \le 1000\)), the number of rows and columns.

The next \(R\) lines contain \(C\) characters each. Character M denotes Mirko's piece, S Slavko's piece and . denotes an empty field.

There is at least one piece per player on the board. Otherwise the game would be over.

In the first and only line of output you need to print exactly two integers. The first integer is the spread of Mirko's pieces and the second of Slavko's pieces.

Scoring: In test cases worth \(20\%\) of total points the number of pieces on the board will be less than or equal to \(5000\). In test cases worth \(60\%\) of total points, the numbers \(R\) and \(C\) will be smaller than or equal to \(300\).

riseoj 작성

출처 COCI 2009/2010 Contest 7