시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 42 25 19 63.333%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1

2 3
SMS
MMS

예제 출력 1

3 5
W3sicHJvYmxlbV9pZCI6IjI4ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWJjOTQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWJjOTRcdWM3NzRcdWM2NDAgXHVjNjAxXHVkNmM4XHVjNzc0XHViMjk0IFx1Y2NiNFx1YzJhNFx1Yjk3YyBcdWJjYzBcdWQ2MTVcdWQ1NWMgXHVjMGM4XHViODZkXHVhY2UwIFx1Y2MzOFx1YzJlMFx1ZDU1OFx1YmE3MCBcdWQ2MDFcdWMyZTBcdWM4MDFcdWM3NzggXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YWMxY1x1YmMxY1x1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBSXHVkNTg5IENcdWM1ZjRcdWM3NTggXHVjY2I0XHVjMmE0XHVkMzEwXHVjNWQwXHVjMTFjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YjQxOFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHViYTg3XHVhYzFjXHVjNzU4IFx1Y2NiNFx1YzJhNCBcdWQwYjkgXHViOWQwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1Y2NiNFx1YzJhNCBcdWQwYjlcdWM3NDAgXHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwJm5ic3A7XHViMzAwXHVhYzAxXHVjMTIwIFx1Y2QxZCZuYnNwOzhcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2U3OFx1YzUyOSBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHViM2M1XHVkMmI5XHVkNTVjIFx1YzgxMFx1Yzc0MCBcdWM4MTBcdWMyMTggXHVhY2M0XHVjMGIwIFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC4mbmJzcDtcdWMwYzFcdWJjOTRcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YWM4Y1x1Yzc4NFx1Yzc3OFx1YzljMFx1Yjc3YyBcdWM1ZWRcdWMyZGMgXHVhZTMwXHVhZDM0XHVkNTY4XHVjNzQ0IFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVhYzAxIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViNDUwJm5ic3A7XHVkMGI5Jm5ic3A7XHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YjJlOCBcdWFjNzBcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWI0NTAgXHViOWQwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhYzcwXHViOWFjXHViMjk0IFx1ZDU1YyBcdWQwYjlcdWM3NzQgXHViMmU0XHViOTc4IFx1ZDBiOVx1Yzc1OCBcdWM3MDRcdWNlNThcdWFlNGNcdWM5YzAmbmJzcDtcdWM3NzRcdWIzZDlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3NzRcdWIzZDlcdWM3NTggXHVkNjlmXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzQgXHViNTRjLCZuYnNwO1x1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM3NzRcdWIzZDkgXHVhY2JkXHViODVjIFx1YzcwNFx1YzVkMCBcdWIyZTRcdWI5NzggXHViOWQwXHVjNzc0IFx1Yzc4OFx1YzViNFx1YjNjNCBcdWJiMzRcdWMyZGNcdWQ1NThcdWFjZTAgXHVjZDVjXHViMmU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMgXHVhYzhjXHVjNzg0IFx1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMGMxXHViYzk0XHVjNzc0XHVjNjQwIFx1YzYwMVx1ZDZjOFx1Yzc3NFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTg5XHVjNzU4IFx1YzIxOCBSXHVhY2ZjIFx1YzVmNFx1Yzc1OCBcdWMyMTggQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoMSAmbGU7IFIsIEMgJmxlOyAxLDAwMCkuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyZuYnNwO1JcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IENcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgJiMzOTtNJiMzOTtcdWM3NDAgXHVjMGMxXHViYzk0XHVjNzc0XHVjNzU4IFx1ZDBiOSwgJiMzOTtTJiMzOTtcdWIyOTQgXHVjNjAxXHVkNmM4XHVjNzc0XHVjNzU4IFx1ZDBiOSwgXHVhZGY4XHViOWFjXHVhY2UwICYjMzk7LiYjMzk7XHVjNzQwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjNzc0XHVjNTdjXHVhZTMwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDBcdWIyOTQgXHVjMGMxXHViYzk0XHVjNzc0XHVjNjQwIFx1YzYwMVx1ZDZjOFx1Yzc3NFx1Yzc1OCBcdWI5ZDBcdWM3NzQgXHVjZDVjXHVjMThjXHVkNTVjIFx1ZDU1OFx1YjA5OFx1YzUyOVx1Yzc0MCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHViYzk0XHVjNzc0XHVjNjQwIFx1YzYwMVx1ZDZjOFx1Yzc3NFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg4OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktSQUxKRVZJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBwbGF5aW5nIGEgY2hlc3MgbGlrZSBnYW1lLiBUaGUgZ2FtZSBpcyBwbGF5ZWQgb24gYSBub24tc3RhbmRhcmQgY2hlc3MgYm9hcmQgc2l6ZWQgUiByb3dzIGJ5IEMgY29sdW1ucy4gRWFjaCBwbGF5ZXIgc3RhcnRzIHdpdGggc29tZSBudW1iZXIgb2YgY2hlc3Mga2luZ3MuIEluIGNoZXNzIGtpbmdzIGNhbiBtb3ZlIGZyb20gdGhlaXIgY3VycmVudCBmaWVsZCB0byBhbnkgb2YgdGhlIDggbmVpZ2hib3VyaW5nIGZpZWxkcy48XC9wPlxyXG5cclxuPHA+UGxheWVyIHNwcmVhZCBpcyBkZWZpbmVkIGFzIHRoZSBjb21wbGV0ZSBzdW0gb2YgZGlzdGFuY2VzIGJldHdlZW4gYWxsIHBhaXJzIG9mIHBpZWNlcyBvZiB0aGUgZ2l2ZW4gcGxheWVyLiBUaGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gcGllY2VzIGlzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgbW92ZXMgcmVxdWlyZWQgZm9yIGJvdGggcGllY2VzIHRvIHJlYWNoIHRoZSBzYW1lIGZpZWxkLiBObyBhY3R1YWwgbW92ZXMgYXJlIHBlcmZvcm1lZCB3aGVuIGNhbGN1bGF0aW5nIHRoZSBkaXN0YW5jZSBhbmQgYXMgc3VjaCBlbmVteSBwaWVjZXMgZG8gbm90IGluZmx1ZW5jZSB0aGUgcmVzdWx0LjxcL3A+XHJcblxyXG48cD5NaXJrbyBrbm93cyB0aGF0IHRoZSBzcHJlYWQgaXMgYSB2aXRhbCBwaWVjZSBvZiBzdHJhdGVnaWMgaW5mb3JtYXRpb24gYW5kIHdvdWxkIGxpa2UgeW91IHRvIG1ha2UgaGltIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIGJvdGggaGlzIGFuZCBTbGF2a28mIzM5O3Mgc3ByZWFkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMgKDEgJmxlOyBSLCBDICZsZTsgMSAwMDApLCBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucy48XC9wPlxyXG5cclxuPHA+TmV4dCBSIGxpbmVzIGNvbnRhaW4gQyBjaGFyYWN0ZXJzIGVhY2guIENoYXJhY3RlciAmIzM5O00mIzM5OyBkZW5vdGVzIE1pcmtvJiMzOTtzIHBpZWNlLCAmIzM5O1MmIzM5OyBTbGF2a28mIzM5O3MgcGllY2UgYW5kICYjMzk7LiYjMzk7IGRlbm90ZXMgYW4gZW1wdHkgZmllbGQuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGF0IGxlYXN0IG9uZSBwaWVjZSBwZXIgcGxheWVyIG9uIHRoZSBib2FyZC4gT3RoZXJ3aXNlIHRoZSBnYW1lIHdvdWxkIGJlIG92ZXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHlvdSBuZWVkIHRvIHByaW50IGV4YWN0bHkgdHdvIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlcnMgaXMgdGhlIHNwcmVhZCBvZiBNaXJrbyYjMzk7cyBhbmQgdGhlIHNlY29uZCBTbGF2a28mIzM5O3MgcGllY2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==