TAMCAM - Tam Cam

no tags 

This problem is based on the story of Tam and Cam, a well-known Vietnamese fairy tale.

One day, Cam put some rice grains and some paddy grains into the cells of a rectangular table of size mxn. There is at most one grain in each cell. Cam asked Tam to take the minimum number of grains from the table so that in each row and each column of the table, the number of rice grains is the same as the number of paddy grains.

Could you help Tam to do the task?

Input

  • The first line contains two positive integers m,n ≤ 100 separated by a space.
  • The ith line in the next m lines contains n characters. The jth character could be "G", "T", or "." depending on whether the corresponding cell contains a rice grain, a paddy grain, or is empty.

Output

  • The first line contains the minimum number of grains that should be taken from the table.
  • The ith line in the next m lines contains n characters. The jth character could be "G", "T", or "." depending on whether there remains a rice grain, a paddy grain, or nothing in the corresponding cell.

Example

Input
4 5
GT.GG
GGTGT
TTGTG
GTGT.	

Output
6
.T.G.
.GTGT
T.GTG
G..T.



Added by:Duc
Date:2009-02-04
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:VNOI Marathon 2009
Round 1
Problem Setter: Lê Minh Hoàng