Largest Rectangle with Uniform Heights

Given an m × n matrix of integers, the task is to find the area of the largest rectangle (submatrix) in which all cells have the same height. In other words, you must identify a submatrix where all entries are equal and compute its area maximized over all possible such submatrices.

Let the matrix be \(A\) with dimensions \(m\) and \(n\). For a uniform submatrix with all entries equal to \(h\), if its area is \(A_{rect}\), then we need to maximize \(A_{rect}\) subject to all values in that rectangle being \(h\). This problem can be solved by iterating over all possible candidate heights that appear in \(A\) and using a histogram-based method to compute the largest rectangle in each transformed row representation.

Input Format: The first line contains two integers \(m\) and \(n\) representing the number of rows and columns. The following \(m\) lines each contain \(n\) integers representing the matrix values.

Output Format: Output an integer indicating the area of the largest rectangle that can be formed with cells of equal height.

inputFormat

The input is read from standard input (stdin). The first line contains two integers \(m\) and \(n\). Each of the next \(m\) lines contains \(n\) space-separated integers representing the matrix.

outputFormat

Print a single integer to standard output (stdout): the area of the largest rectangle in the matrix where all cells have the same height.

## sample

3 3
1 1 1
1 1 1
1 1 1

9

</p>