웅골리안트의 자손

웅골리안트의 자손인 거미들이 어둠숲으로 퍼지고 있다. 거대 거미는 자기가 자리 잡은 나무를 떠나지 못하지만, 바로 옆 나무에 알을 낳는다. 알은 금방 부화해 새 거미가 되고, 그 거미가 다시 옆 나무에 알을 낳는다.

거미가 사는 나무와 거미가 없는 나무가 표시된 어둠숲 지도가 주어진다. 거미가 더 퍼질 수 없을 때까지 퍼지고 난 뒤의 지도를 구하라.

이 문제에서 인접은 동서남북 네 방향만 뜻한다. 대각선으로 맞닿은 두 나무는 인접하지 않는다.

입력은 지도 여러 개로 이루어진다. 각 지도의 첫 줄에는 지도의 너비 $W$와 높이 $H$가 주어진다. 이어지는 $H$개의 줄에는 길이가 $W$인 문자열이 주어져 어둠숲의 배치를 나타낸다. S는 거미가 사는 나무, T는 거미가 없는 나무, .(마침표)는 나무가 없는 숲 바닥이다.

$W$와 $H$가 모두 0인 줄이 나오면 입력이 끝난다. 이 줄은 처리하지 않는다.

지도마다 거미가 더 퍼질 수 없게 된 뒤의 어둠숲 지도를 출력한다. 지도와 지도 사이에 빈 줄을 넣지 않는다.