Largest Flower Bouquet Subgrid

Given an N x M grid containing only '0' and '1', where '1' represents a flower and '0' represents an empty cell, your task is to find the largest contiguous subgrid (rectangle) that contains only flowers. The area of the rectangle is defined as the number of cells in it. After determining this maximum area, choose two positive integers h and w such that h * w equals the area and the difference between w and h is minimized (i.e., the factors are as close as possible). If no flower exists in the grid, output 0 0.

The solution involves using a histogram technique by iterating row by row and computing the maximum rectangle area in a histogram using a stack. Finally, you are to factorize the maximum area to obtain the rectangle dimensions with minimal difference.

The formula for choosing the factors can be summarized as follows: [ \text{Let } A = h \times w, \text{ find } (h, w) \text{ such that } h \times w = A \text{ and } |w - h| \text{ is minimized.} ]

inputFormat

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

• The first line contains two integers N and M, representing the number of rows and columns respectively.
  
• This is followed by N lines, each containing a string of length M. Each character is either '0' or '1', where '1' indicates a flower and '0' indicates an empty cell.

outputFormat

Output to standard output (stdout) two integers separated by a space. These integers represent h and w, the dimensions of the largest contiguous subgrid of flowers (i.e., the rectangle with the maximum area and with factors as close as possible). If there is no flower (i.e., maximum area is 0), output '0 0'.## sample

6 5
10111
10111
11111
10010
00111
11111

3 3