시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 15 9 52.941%

문제

회린이는 타워디펜스 게임 제작을 하고 있었다. 그러던 어느날 재혁이가 개발노트를 빼앗기 위해 회린이의 회사를 침공한다. 그러나 재혁이는 자신이 뭔가 하는 걸 귀찮아하기 때문에 자신이 직접 침입하지 않고 자신의 클론들을 여러 명 만들어 회사에 침투시켰다.

회린이의 회사는 R×S의 크기를 가진 직사각형 영역이며, 회사 안에는 몇 개의 타워가 있다. 이 타워에는 대포가 90도 간격으로 정확히 두 개가 달려 있는데, 이 말은 한 번 대포를 발사할 때 다음 4가지 중 하나의 조합으로 발사가 가능하다는 것이다.

  1. 왼쪽과 아래쪽으로 동시에 발사
  2. 아래쪽과 오른쪽으로 동시에 발사
  3. 오른쪽과 위쪽으로 동시에 발사
  4. 위쪽과 왼쪽으로 동시에 발사

대포를 발사하면 일직선으로 대포알이 날아간다. 대포알이 재혁이의 클론과 부딪히면 클론만 죽게 되며 대포알은 여전히 같은 방향으로 날아간다. 대포알이 벽에 부딪히면 대포알만 파괴되고 벽은 멀쩡하다(벽은 크고 힘세기 때문이다). 그러나 대포알이 다른 타워에 부딪히면 그 타워는 무너지고 만다(타워는 연약하기 때문이다).

회린이는 모든 타워를 적절히 회전하여, 단 한 번만 모든 대포를 동시에 발포하여 모든 클론들을 쳐부수고 싶다. 또한 타워 하나하나는 굉장히 비싸기 때문에 어떤 타워도 손상되어서는 안 된다. 회린이를 도와 클론들을 무찌르시오.

입력

첫 번째 줄에 회사의 크기 R, S가 주어진다. (1 ≤ R, S ≤ 100)

그 다음 R줄에 걸쳐 S칸씩 회사의 지도가 주어진다.

지도의 각 대문자 'T'는 타워를, 소문자 'n'은 재혁이의 클론을, 특수문자 '#'은 벽을, 특수문자 '.'은 빈 공간을 나타낸다.

항상 정답이 존재하는 경우만 주어지지만, 정답이 유일하지 않을 수도 있다.

출력

입력에서 주어진 지도에서 각 타워의 위치를 '1', '2', '3', '4' 중에서 알맞은 방향을 나타내는 번호를 골라 덮어씌워서 출력하시오. 각 번호가 의미하는 방향은 위에서 설명한 대로다. 반드시 모든 타워의 방향을 출력해야 한다.

예제 입력

9 13
.............
...........n.
.n.T..nnnn#..
.............
.T#n..n....T.
.............
.n.T..T....n.
.............
......n......

예제 출력

.............
...........n.
.n.3..nnnn#..
.............
.4#n..n....4.
.............
.n.1..2....n.
.............
......n......

힌트