Tower Defense

Hoerin is making a tower defense game. One day, Jaehyuk attacks Hoerin's company to steal the development notes, but because he does not want to do the work himself, he creates many clones and sends them in.

Hoerin's company is a rectangular grid of size R×S. Several towers are placed inside the grid. Each tower has exactly two cannons mounted at a right angle, so when it fires, it must choose one of the following four direction pairs.

1. Left and down
2. Down and right
3. Right and up
4. Up and left

A cannonball travels in a straight line in the direction it was fired. If it hits one of Jaehyuk's clones, only the clone is removed, and the cannonball keeps flying in the same direction. If it hits a wall, only the cannonball is destroyed and the wall remains. However, if it hits another tower, that tower collapses.

Hoerin wants to rotate every tower, then fire all cannons simultaneously exactly once, so that every clone is removed. No tower may be damaged. Determine a direction for each tower that satisfies these conditions.

The first line contains the company size R and S. (1 ≤ R, S ≤ 100)

The next R lines contain S characters each and describe the company map.

In the map, uppercase T is a tower, lowercase n is one of Jaehyuk's clones, # is a wall, and . is an empty cell.

Every input is guaranteed to have at least one valid answer. The answer may not be unique.

Print the given map after replacing each tower cell T with one of the digits 1, 2, 3, and 4. The meaning of each digit is the corresponding direction pair from the problem statement.

You must output a direction for every tower.