시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 13 13 76.471%

문제

상범이와 영훈이는 체스를 변형한 새롭고 참신하며 혁신적인 게임을 개발했다. 이 게임은 R행 C열의 체스판에서 플레이되는 게임이다. 각 플레이어는 몇개의 체스 킹 말을 가지고 시작한다. 체스 킹은 상하좌우 대각선 총 8방향으로 한 칸씩 이동할 수 있다.

이 게임의 가장 독특한 점은 점수 계산 방법이다. 상범이가 만든 게임인지라 역시 기괴함을 자랑하는데, 각 플레이어의 모든 두 킹 간의 최단 거리의 합이 점수가 된다. 이때 두 말 사이의 최단 거리는 한 킹이 다른 킹의 위치까지 이동하기 위해 필요한 이동의 횟수이다. 이 때, 이러한 이동 경로 위에 다른 말이 있어도 무시하고 최단 거리를 계산해야 한다.

현재 게임 판의 상태가 주어졌을 때, 상범이와 영훈이의 점수를 구해보자.

입력

첫 번째 줄에는 행의 수 R과 열의 수 C가 주어진다(1 ≤ R, C ≤ 1,000).

다음 R개의 줄에는 C개의 문자가 주어지는데, 'M'은 상범이의 킹, 'S'는 영훈이의 킹, 그리고 '.'은 빈 칸을 이야기한다.

체스판에는 상범이와 영훈이의 말이 최소한 하나씩은 존재한다.

출력

첫 번째 줄에 상범이와 영훈이의 점수를 공백으로 구분하여 출력한다.

예제 입력

2 3
SMS
MMS

예제 출력

3 5

힌트