Largest Rectangle in a Character Grid

Given a grid of characters with dimensions ( n \times m ), your task is to determine the area of the largest rectangle that is fully filled with the character '#' (hash). The rectangle must be contiguous and aligned with the grid axes. If no such rectangle exists, output 0.

The problem can be approached by computing, for each cell, the number of consecutive '#' characters to its left. Then, for each cell containing '#', by iterating upward, you can determine the maximum area rectangle ending at that cell. Formally, if ( w(i,j) ) denotes the consecutive count of '#' ending at cell ( (i,j) ), then the area for a rectangle ending at ( (i,j) ) and extending upward to row ( k ) is given by ( \text{area} = \min_{r=k}^{i} w(r,j) \times (i - k + 1) ).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer ( n ) representing the number of rows of the grid.
• The next ( n ) lines each contain a string that represents a row of the grid.

All rows are guaranteed to have the same length.

outputFormat

Output a single integer to standard output (stdout), which is the area of the largest rectangle composed solely of '#' characters. If there is no '#' present in the grid, output 0.## sample

3
a#b.
a###
c###

6