Frogshold Distance

A scourge of frogs is devastating the crops in Byteotia. To combat them, Farmer Byteasar has deployed peculiar "scarefrogs" at certain positions in his rectangular field. Every frog that hops from one point to another (moving only in the four cardinal directions with unit steps) chooses its route in order to maximize its distance from the nearest scarefrog at every inter‐leap point.

The scarefrog-distance of a route is defined as the minimum, over all points on the route, of the Manhattan distance from that point to the closest scarefrog. The frogshold distance is the maximum achievable scarefrog-distance over all possible routes from the source to the destination. Your task is to compute the square of this frogshold distance.

Input Specifications: The input begins with two positive integers R and C, representing the number of rows and columns of the field. This is followed by R lines, each containing a string of length C. The grid contains the following characters:

• S denoting the source point (starting position of the frog),
• T denoting the destination point,
• # representing a scarefrog (a “bad point”), and
• . representing an empty cell.

Output Specifications: Output a single integer: the square of the maximum possible scarefrog-distance that a frog can maintain along a path from S to T. A valid path is one in which the Manhattan distance from every visited cell to the nearest scarefrog is at least d, and you are to maximize d. (Recall that the Manhattan distance between cells (r1, c1) and (r2, c2) is given by \( |r1 - r2|+|c1 - c2| \)).

Note: It is guaranteed that there is at least one scarefrog in the grid.

inputFormat

The first line contains two integers R and C (1 ≤ R, C ≤ 1000), the number of rows and columns in the grid. Each of the following R lines contains a string of exactly C characters. The grid consists of characters:

• S for the starting point
• T for the destination
• # for a scarefrog
• . for an empty cell

It is guaranteed that there is exactly one S and one T, and at least one scarefrog ('#') exists in the grid.

outputFormat

Output a single integer, the square of the maximum achievable scarefrog-distance along any valid path from S to T.

sample

5 5
S....
.....
..#..
.....
....T

4