Largest Odd Submatrix

Given an n × m matrix, your task is to find the largest rectangular submatrix in which every number is odd. In other words, you must output the maximum area (i.e. the number of elements) of a contiguous block of cells, where each cell contains an odd integer. If there is no such submatrix, output 0.

This problem can be efficiently solved by first converting the matrix into a binary matrix indicating odd (1) or even (0) numbers, and then, for each row, constructing a histogram that represents consecutive odd numbers. The well-known 'largest rectangle in a histogram' algorithm can then be applied to find the maximum rectangle area for that row.

inputFormat

Input is given via standard input (stdin). The first line contains two integers n and m denoting the number of rows and columns respectively. This is followed by n lines, each containing m space-separated integers representing the matrix elements.

outputFormat

Output a single integer to standard output (stdout) which is the area (i.e., number of elements) of the largest rectangular submatrix that contains only odd numbers. If no such submatrix exists, output 0.## sample

1 1
1

1