题目描述

Mirko 和 Slavko 在一个 $R \times C$ 的棋盘上游戏。他们各自在棋盘上摆放一定数量的王——王每步可以任选 $8$ 个方向中的一个移动 $1$ 步。现规定：

• 两个王之间的「距离」为其中一个王移动到另一个王所在棋格所需的最少步数。
• 一个玩家的「扩张度」为该玩家所有的王两两之间距离总和。

分别求出 Mirko 和 Slavko 的「扩张度」。

输入格式

第一行，两个整数 $R,C$。

接下来的 $R$ 行，每行 $C$ 个字符 $\texttt M$ / $\texttt S$ / $\texttt .$，分别表示 Mirko 的王、Slavko 的王和空位。数据保证每一方在棋盘上至少有一个王。

输出格式

输出两个整数，分别表示 Mirko 和 Slavko 的「扩张度」。

2 3
SMS
MMS

3 5

2 3
S.M
M..

2 0

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

10 13

提示

【数据规模与约定】

• 对于 $20\%$ 的数据，棋盘上王的总数不超过 $5000$。
• 对于 $60\%$ 的数据，$R,C \le 300$。
• 对于 $100\%$ 的数据，$1 \le R,C \le 1000$。

【提示与说明】

题目译自 COCI 2009-2010 CONTEST #7 Task 5 KRALJEVI。

本题分值按 COCI 原题设置，满分 $120$。