Cat's Diagonal Fish Feast

Consider a rectangular pool represented as a binary matrix where (0) indicates an empty position and (1) indicates the presence of a fish. The clever cat has transferred all her fish into the pool and now wonders how to eat as many fish as possible in a single bite. She notices that if she can find a square submatrix in which exactly one of the two diagonals (either the main diagonal or the anti-diagonal) is filled with fish (i.e. all (1)s) and every other cell in that square is empty (i.e. (0)), she can eat all the fish lying on that diagonal in one go. The number of fish eaten is equal to the side length of the submatrix. Note that a submatrix of size (1 \times 1) is valid if its only cell is (1).

Your task is to find the maximum number of fish the cat can eat in one bite, i.e. the maximum side length among all square submatrices satisfying the above condition. If no such submatrix exists, output (0).

inputFormat

The first line contains two integers (m) and (n) ((1 \le m, n \le 1000)) representing the number of rows and columns of the matrix. Each of the following (m) lines contains (n) space-separated integers (either (0) or (1)) representing the matrix.

outputFormat

Output a single integer: the maximum number of fish that can be eaten in one bite (i.e. the side length of the appropriate square submatrix). If no valid submatrix exists, output (0).

sample

3 3
1 0 0
0 1 0
0 0 1

3