브레이크가 고장난 카트

크기가 $H \times W$인 격자판이 있다. 이 격자판의 몇몇 격자에는 박스 모양의 장애물이 놓여 있다.

다오는 이 격자판 위에서 카트를 타며 이동하고 있다.

어느 날 다오가 타는 카트의 브레이크가 고장이 났다. 브레이크 고장으로 카트는 위, 아래, 왼쪽, 오른쪽 중 한 방향을 정해서 이동하면, 장애물에 부딪혀서 멈출 때까지 같은 방향으로 이동한다.

이때, 카트와 부딪힌 장애물의 면에는 파란색 페인트가 묻는다. 가장 처음을 제외하면, 장애물과 부딪힌 다음에 카트가 멈춘 후에만 방향을 바꾸어 이동할 수 있음에 유의하라.

현재 다오의 위치와 격자판에 놓인 장애물의 정보가 주어질 때, 여러분은 페인트가 묻은 면의 개수가 가능한 많아지도록 다오가 이동하는 방법을 구해야 한다.

같은 면에 카트가 여러 번 부딪혀도, 페인트가 묻은 면의 개수를 셀 때에는 한 번만 세어야 함에 유의하라.

격자판의 모든 테두리 격자에는 장애물이 놓여 있기 때문에, 다오가 격자판 밖으로 나가는 일은 발생하지 않는다.

위와 같은 예시를 보자. 다오가 위, 아래, 왼쪽, 위, 아래, 오른쪽, 위, 아래로 움직이면 아래와 같이 가능한 모든 면에 페인트가 묻는다.

입력 형식

첫 줄에 격자판의 크기를 나타내는 두 정수 $H$와 $W$가 공백으로 구분되어 주어진다. ($3 \le H, W \le 25$)

이어지는 $H$ 개의 줄에는 격자판의 상태를 나타내는 길이 $W$의 문자열이 주어진다. 이 문자열은 문자 ., #, S로만 이루어져 있으며, 각각 빈 격자, 장애물이 놓인 격자, 초기에 다오가 있는 격자임을 의미한다.

문자 S는 정확하게 한 개 주어진다. 각 문자열의 첫 번째 문자와 마지막 문자, 그리고 첫 문자열과 마지막 문자열의 모든 문자는 #이다.

출력 형식

첫 줄에 다오가 이동을 마친 후, 페인트가 묻은 장애물의 면의 개수를 출력한다.

그다음 줄에 다오의 이동 방법을 나타내는 문자열을 출력한다. 이 문자열은 문자 W, A, S, D로만 이루어져야 하며, 각각 위, 왼쪽, 아래, 오른쪽의 방향을 의미한다. 출력하는 문자열의 길이는 $10\,000\,000$을 넘지 않아야 한다. 출력하는 문자열의 길이가 가장 짧을 필요가 없음에 유의하라.

예제

3 5
#####
#.S.#
#####

8
WSAWSDWS

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

• $S$ : 미션에서 받을 수 있는 최대 점수
• $P$ : 미션에 대한 참가자의 점수
• $\alpha$ : 미션마다 정해진 상수
• $\beta$ : 참가자의 출력대로 이동했을 때 페인트가 묻은 면의 수

이때, 미션에 대한 참가자의 점수 $P$는 $S \times \lfloor 100 \times \frac{\beta}{\alpha} \rfloor \times \frac{1}{100}$ 의 값을 $0.1$ 단위로 버림한 값이다.

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 제약 조건을 지키지 않는 등) $P = 0$이다.

각 미션의 정보는 다음과 같다.

미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설