최대한 빠르게

다오는 크기가 $H \times W$인 격자판 위에서 카트를 타며 이동하고 있다. 격자판의 몇몇 칸에는 박스 모양의 장애물이 있어서 카트가 들어가거나 지나갈 수 없으며, 다오는 매번 위, 아래, 왼쪽, 오른쪽 중 한 방향을 정해 일정 거리만큼 이동할 수 있다.

구체적으로, 처음에 다오는 원하는 방향으로 카트를 한 칸씩 움직일 수 있다. 격자판의 몇몇 칸에는 아이템이 놓여 있는데, 만약 다오의 카트가 정확히 아이템이 놓인 칸에서 멈추게 되면, 한 번에 이동할 수 있는 최대 거리가 영구적으로 $1$만큼 늘어나고 아이템은 격자판에서 사라진다. 즉, 지금까지 아이템을 $X$개 먹었다면, 매번 원하는 방향으로 최대 $X + 1$칸 움직일 수 있다. 단, 이동 중에 장애물이 있는 칸을 통과하거나 격자판 밖으로 나갈 수는 없다.

예를 들어, 아래 그림에서 다오가 지금까지 $1$개의 아이템을 먹었다고 하자. 아래와 오른쪽으로는 최대 $2$칸 이동할 수 있으며, 왼쪽으로는 장애물에 가로막혀 최대 $1$칸만 이동할 수 있다. 위로 $1$칸 이상 이동하면 격자판을 벗어나게 되므로 위로는 이동할 수 없다.

현재 다오의 위치, 격자판에 놓인 장애물과 아이템의 정보, 그리고 다오가 가고자 하는 목적지의 위치가 주어지면, 여러분은 이동 횟수를 최소화하면서 다오가 목적지까지 가는 경로를 구해야 한다.

입력 형식

첫 줄에 격자판의 크기를 나타내는 두 정수 $H$와 $W$, 그리고 격자판에 놓인 아이템의 개수를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($13 \le H, W \le 49;$ $0 \le K \le 30$)

이어지는 $H$개의 줄에는 격자판의 상태를 나타내는 길이 $W$의 문자열이 주어진다. 이 문자열은 문자 ., #, @, S, T로만 이루어져 있으며, 각각 빈 칸, 장애물이 놓인 칸, 아이템이 놓인 칸, 다오의 시작 위치, 다오의 목적지를 의미한다.

$H$개의 문자열 전체에서 문자 S와 T는 각각 정확히 $1$개 주어지며, 문자 @는 정확히 $K$개 주어진다.

출력 형식

첫 줄에 다오의 이동 횟수 $q$를 출력한다. $q \le 5\,000$를 만족해야 한다.

그다음 줄부터 총 $q$개의 줄에 걸쳐, 다오의 이동 방법을 나타내는 문자열을 출력한다. 이 문자열은 문자 $c$와 양의 정수 $d$로 이루어져 있어야 하며, 각각 이동 방향과 이동 거리를 의미한다. $c$는 문자 W, S, A, D 중 하나여야 하며, 각각 위, 아래, 왼쪽, 오른쪽 방향을 의미하고, $d$는 다오의 이동 거리를 의미한다.

예제

5 5 4
@...@
.###.
.#S#.
.#@.@
T####

5
S 1
D 2
W 3
A 4
S 4

채점 방식

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

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

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

• $S$: 미션에서 받을 수 있는 최대 점수
• $P$: 미션에 대한 참가자의 점수
• $\alpha$, $\beta$: 미션마다 정해진 상수 (단, $\alpha>\beta$)
• $q$: 참가자의 출력에서의 이동 횟수

이때, 미션에 대한 참가자의 점수는 $P$를 $0.1$ 단위로 버림한 값이다. 즉, $\alpha$는 미션에서 $0$점을 받게 되는 이동 횟수의 하한, $\beta$는 미션에서 만점을 받기 위한 이동 횟수를 나타내는 상수이다.

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

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

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

해설