CWB - Chipmunks with Brain

no tags 

There is a Chipmunk with "Brain" and he want to dig holes in a yard to store his food.
There is a rectangular yard which is divided into unit cells, initially having some holes(H) and sand(S). The chipmunk can dig one row at a time, But he have to dig all the sand(S) positions simultanously and due to this holes(H) which are already there got filled with sand.

Example:
Suppose a Row is "SHSHH" then after digging the row becomes "HSHSS" i.e all "S" replace with "H" and vice versa.

Now Chipmunk wants to have a large square of holes somewhere in the yard. The sides of square must be parallel to the sides of the yard. Find a sequence of turns that produces the largest possible square of holes somewhere in the yard and help him to find the area of that square.

Input

Given two interger Rows(R) and column(C) (1<=R,C<=30)
Next line contain a RxC rectangular yard of sand (S) and hole (H).

Output

Print largest "Area of the Square" that can be obtain after sequence of turns.

Example

Input:
2 2
SS
HH
Output: 4

Input:
5 1
H
S
H
H
H
Output: 1

hide comments
:D: 2016-10-21 22:39:35

Just to clarify, you can only change rows. That is, columns can't be processed in any way.

J_P: 2014-08-30 19:09:41

nice one.. :)

BLANKRK: 2014-06-25 17:35:49

done!! :)

Mitch Schwartz: 2014-06-19 01:04:17

The optimisation possibilities for this problem are kind of interesting. It could be nice to have a version with higher constraints and multiple cases per input file for proper speed comparison. (And uniform random input wouldn't be sufficient, it would require a little thought.)

shiv prasad chabarval: 2014-06-10 20:00:59

@Quantum : what do u mean by one row at a time ?


Added by:P_Quantum
Date:2014-04-17
Time limit:0.170s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All