Maximal Rectangle of Dots

You are given a grid consisting of * and . characters, where * represents an obstacle and . represents an empty space. Your task is to determine the area of the largest rectangle that contains only . characters.

The rectangular region must be aligned with the grid. In other words, its sides must be parallel to the grid's rows and columns.

Note: The solution must handle grids of varying sizes and configurations efficiently.

Hint: Use dynamic programming techniques along with a stack-based approach to compute the largest rectangle area in a histogram derived from the grid rows.

The mathematical formulation of the problem is as follows:

If we denote the grid as an \(n \times m\) matrix \(A\) with entries \(a_{ij}\), then for each row, we compute a histogram of heights \(h_j\) such that \(h_j = h_j+1\) if \(a_{ij} = '.'\) and \(0\) otherwise. The answer is the maximum rectangle area obtained by applying the largest rectangle in histogram algorithm to these heights.

inputFormat

The input is read from stdin and is in the following format:

n m
row1
row2
... 
rown

Here, the first line contains two integers \(n\) and \(m\), representing the number of rows and columns of the grid respectively. Each of the subsequent \(n\) lines contains a string of length \(m\) consisting only of the characters * and ..

outputFormat

Output a single integer to stdout — the area of the largest rectangle consisting solely of . characters.

## sample

5 6
******
*...**
*.*.**
*.*.**
**.***

3