탐험 로봇

타르라크는 먼바다의 새로운 지역을 탐험하려고 한다. 이 지역은 $R$ 행 $C$ 열의 격자 모양이며, 각 격자 칸은 바다 혹은 육지이다. 타르라크는 이 지역에 섬 하나당 탐험 로봇 하나를 보내서 섬을 탐험하려고 한다. 여기서 섬은 상하좌우 방향으로 연결된 육지를 의미한다.

타르라크는 이 지역의 지도를 가지고 탐험 로봇을 만들려고 했으나 지도의 일부분이 찢어졌을 수도 있다는 얘기를 들었다. 어쩌면 좋을지 고민하던 타르라크는 찢어지지 않은 부분을 사용해서, 필요한 탐험 로봇 개수의 최솟값과 최댓값을 구하기로 했다. 단, 지도 밖은 모두 바다인 것을 알고 있다.

각 격자가 바다, 육지, 혹은 찢어진 부분으로 표시된 $R$ 행 $C$ 열의 격자를 입력으로 받아서 필요한 탐험 로봇 개수의 최솟값 혹은 최댓값을 구하는 프로그램을 작성하여라.

입력 형식

첫 줄에는 지도의 크기를 나타내는 두 정수 $R$와 $C$가 공백으로 구분되어 주어진다. $(1 \le R \times C \le 1\,000)$

둘째 줄에는 문자열 $S$가 주어진다. $S$는 min 또는 max 이다. $S$가 min이면 필요한 탐험 로봇 개수의 최솟값을, max이면 필요한 탐험 로봇 개수의 최댓값을 구해야 한다는 의미이다.

다음 $R$ 개의 줄 중 $i$ 번째 줄에는 L, S 또는 ?로 이루어진 길이 $C$의 문자열 $M_i$가 주어진다. 이 문자열의 $j$ 번째 문자는 지도의 위에서 부터 $i$ 번째 행, 오른쪽에서 부터 $j$ 번째 열을 의미한다. 이 문자가 L인 경우에는 육지, S인 경우에는 바다, ?인 경우에는 찢어진 부분을 의미한다.

출력 형식

$S$가 min인 경우에는 필요한 탐험 로봇 개수의 최솟값, max이면 필요한 탐험 로봇 개수의 최댓값을 첫 줄에 출력한다.

예제 1

4 5
min
L????
S????
S????
S????

1

예제 2

4 5
max
L????
S????
S????
S????

9

예제 3

1 1
max
S

0

예제 설명

다음은 1번과 2번 예제를 표현한 지도이다.

지도 전체가 아래와 같은 경우, 섬이 한 개이므로, 탐험 로봇이 한 개 필요하며, 이것이 최솟값이다.

지도 전체가 아래와 같은 경우, 섬이 아홉 개이므로, 탐험 로봇이 아홉 개 필요하며, 이것이 최댓값이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설