Symmetrical Submatrix Finder

In this problem, you are given an n×n binary matrix (composed of characters '0' and '1') representing a square pattern. In this square, the digit '0' represents a white cell and the digit '1' represents a black cell. The pattern may have different kinds of symmetries. In class, the following symmetries were defined:

• Axis symmetry: A square is axis symmetric if there exists at least one reflection axis (horizontal, vertical, or either of the two diagonals) such that the square remains unchanged after the reflection.
• 180° rotational symmetry: A square is 180° symmetric if it remains unchanged when rotated 180° about its center.
• 90° rotational symmetry: A square is 90° symmetric if it remains unchanged when rotated 90° clockwise about its center. (Note that a 90° symmetric square is also 180° symmetric.)
• 4-symmetry: A square is said to be 4-symmetric if it possesses two perpendicular axes of symmetry. It can be shown that a square is 4-symmetric if and only if it is both 180° symmetric and axis symmetric.
• 8-symmetry: A square is 8-symmetric if it is symmetric with respect to all 4 reflection axes. Equivalently, a square is 8-symmetric if and only if it is both 90° symmetric and axis symmetric.

Your task is to find, within the given n×n matrix, a contiguous submatrix (i.e. a sub-square formed by consecutive rows and columns) which exhibits each of the five types of symmetry. For each symmetry type (8-symmetry, 90° symmetry, 4-symmetry, 180° symmetry, and axis symmetry), output the maximum side length of a contiguous submatrix that satisfies the symmetry.

Note: A submatrix is defined by choosing consecutive rows and consecutive columns from the original matrix.

Input Format: The first line contains an integer n, the side length of the large square. The following n lines each contain a string of n characters (each character is either '0' or '1') representing the rows of the matrix.

Output Format: Output five integers separated by a space. They represent the maximum side length of a contiguous submatrix that is 8-symmetric, 90° symmetric, 4-symmetric, 180° symmetric, and axis symmetric, respectively.

inputFormat

The input begins with a line containing the integer n. The next n lines each contain a string of length n, composed solely of the characters '0' and '1'.

outputFormat

Output a single line with five space‐separated integers indicating the maximum side lengths of submatrices satisfying 8-symmetry, 90° symmetry, 4-symmetry, 180° symmetry, and axis symmetry, respectively.

sample

3
010
101
010

3 3 3 3 3