Largest Empty Square

Given a grid consisting of H rows and W columns, each cell is either empty (represented by '.') or contains a nut (represented by 'N'). Your task is to determine the area of the largest contiguous square sub-grid that contains only empty cells.

The problem can be solved using dynamic programming. For each cell (i, j) that is empty, the side length of the largest square ending at that cell is given by:

( dp[i][j] = \min(dp[i-1][j],, dp[i][j-1],, dp[i-1][j-1]) + 1 )

The answer is the square of the maximum side length found in the grid.

inputFormat

The first line contains two integers H and W separated by a space, representing the number of rows and columns, respectively. Each of the next H lines contains a string of length W that represents a row of the grid. The characters in the string are either '.' (empty) or 'N' (nut).

outputFormat

Output a single integer — the area of the largest contiguous square that contains only empty cells.## sample

5 5
N....
..N..
.....
.N...
.....

9