상자 밀기

정사각형 칸으로 이루어진 2차원 미로 안에 서 있다고 상상해 봅시다. 각 칸은 바위로 막혀 있거나 비어 있습니다. 지금 서 있는 칸에서 북, 남, 동, 서 중 한 방향으로 인접한 빈 칸으로 한 칸 이동할 수 있으며, 이렇게 빈 칸으로 옮겨 가는 것을 걷기라고 부릅니다.

빈 칸 중 하나에는 상자가 놓여 있습니다. 상자와 붙어 있는 칸에 서서 상자 쪽으로 걸어가면 상자를 밀 수 있습니다. 그러면 상자는 바로 앞의 빈 칸으로 한 칸 밀려나고, 당신은 상자가 있던 칸으로 들어갑니다. 이 동작을 밀기라고 합니다. 상자는 오직 밀어서만 움직일 수 있으므로, 한 번 구석으로 밀어 넣으면 다시는 빼낼 수 없습니다.

빈 칸 중 하나는 목표 칸입니다. 걷기와 밀기를 적절히 사용하여 상자를 목표 칸까지 옮기는 것이 목표입니다. 상자가 매우 무겁기 때문에, 밀기 횟수를 최소로 하고 싶습니다.

입력은 여러 개의 미로로 이루어져 있습니다. 각 미로는 행의 수 $r$과 열의 수 $c$(둘 다 $20$ 이하)를 담은 한 줄로 시작합니다.

이어지는 $r$개의 줄에는 각각 $c$개의 문자가 있어 미로의 한 행을 나타냅니다. 각 문자의 의미는 다음과 같습니다.

• # — 바위로 가득 찬 칸
• . — 빈 칸
• S — 당신의 시작 칸(빈 칸)
• B — 상자의 시작 칸(빈 칸)
• T — 목표 칸(빈 칸)

모든 미로에는 S, B, T가 각각 정확히 하나씩 있습니다. 입력은 0 0이 적힌 줄로 끝나며, 이 줄은 미로가 아닙니다.

미로에 나타난 순서대로 $1, 2, 3, \dots$ 번호를 매깁니다. 각 미로에 대해 먼저 Maze #k 줄을 출력합니다. 여기서 k는 미로의 번호입니다.

다음 줄에는 결과를 출력합니다.

• 상자를 목표 칸으로 옮길 수 없다면 Impossible. 을 출력합니다.
• 그렇지 않으면 두 정수를 공백 하나로 구분하여 출력합니다. 첫 번째 정수는 가능한 최소 밀기 횟수이고, 두 번째 정수는 그 최소 밀기 횟수를 사용하는 모든 방법 중에서 총 이동 횟수(걷기와 밀기의 합)가 최소가 되는 값입니다.

각 미로를 출력한 뒤에는 빈 줄을 하나 출력합니다.