Problem E - Reforestation Plan

Deforestation is a major environmental concern for all of us. There can be many causes that lead to deforestation, some are natural causes such us forest degradation or wildfires, but many other causes can the result of direct or indirect human intervention, for example sudden clearcutting or slash-and-burn for agriculture and grazing animals, urban development, acid rain and deliberate fires. Deforestation of tropical rainforest has attract most attention, but the problem is far worse on other forests. Naturally, this leads to loss of biodiversity.

Many governments have started to pay attention to this problem and have also understood that forest management with long-term plans not only can reverse deforestation but also be an economic asset.

The Portuguese government has also a reforestation plan to recover its forests. It was conceived taking into consideration many factors, thus achieving an internal representation plan. The plan, however, is not in an easy readable format to be used by the tree plantation workers.

A reforestation plan is represented by placing numbers on a grid drawn on top of a region map. A number on a grid-cell represents the number of trees that are adjacent (horizontally, vertically and diagonally). Grid-cells with numbers cannot have a tree in them and a tree cannot be adjacent (in all directions) to any other tree.

You have been invited to produce a readable representation of the reforestation plan. The figure below illustrates a plan in its internal representation and one corresponding readable format ('T' means a tree):

   212   
1            
1   3      
            1
-->
T         T
      T      
               
   T   T   
Internal Representation   Readable Representation

Problem

Given a plan in its internal representation, your task is to print the corresponding readable plan. A plan is a matrix NxM of integers, greater or equal zero, where N and M are the number of rows and columns. To avoid multiple solutions, you should decide to build the readable map with the minimum possible number of trees. In case there are several one respecting this criteria, youl should choose the one that allocates trees to the top-left as most as possible, that is, if you concatenate all lines of the grid, the one which would be lexicographically smaller, considering that a tree would be "smaller" than an empty space. You can see two examples of this ordering in the figure below:

T..T                 .T.T               .T.T                 .T..
.... is smaller then ....          and  .... is smaller than ...T
T..T                 T..T               ...T                 T...

Input

The first line of input includes two numbers N and M (with 1<N,M<10) that define the grid for the map. The next N lines include a sequence of M of integers, greater or equal zero. A -1 value indicates a cell without information. A zero or a positive number, indicates the number of trees that are adjacent to that cell.

Output

The output must be the readable grid map. A tree should be written as 'T' and a '.' represents an "empty cell". If there several possible readable representations, choose the one that respects the disambiguation criteria defined above.

You can assume that the input will always be valid and that at least one readable representation of it will be possible.

Sample Input

4 5
-1 2 1 2 -1
1 -1 -1 -1 -1
1 -1 3 -1 -1
-1 -1 -1 -1 1

Sample Output

T...T
..T..
.....
.T.T.

CPUP 2007
Universidade do Porto
(10/10/2007)