Description

Mr. Zhang is explaining symmetry patterns of squares in class. For simplicity, he uses a $01$ matrix to represent a square pattern: divide the square into an $n\times n$ grid, where $0$ represents a white cell and $1$ represents a black cell.

He first talks about easy-to-see reflection symmetry. A square has $4$ axes of symmetry: the horizontal midline, the vertical midline, and the two diagonals. If a square pattern remains unchanged after reflecting across one symmetry axis, it is called an axis-symmetric pattern. For example, the following two patterns are both axis-symmetric.

100  010
100  101
111  000

Mr. Zhang then explains rotational symmetry of squares. If a square pattern remains unchanged after rotating $180$ degrees around its center, it is called a $180$-degree symmetric pattern. If it remains unchanged after rotating $90$ degrees clockwise around its center, it is called a $90$-degree symmetric pattern. For example, in the following two patterns, the left one is $180$-degree symmetric, and the right one is $90$-degree symmetric.

0011  1011
1110  1110
0111  0111
1100  1101

Mr. Zhang continues: if a square pattern has two perpendicular axes of symmetry, it is called a $4$-symmetric pattern; if it is symmetric with respect to all $4$ axes, it is called an $8$-symmetric pattern. By definition, a $90$-degree symmetric pattern is also a $180$-degree symmetric pattern, and an $8$-symmetric pattern is also a $4$-symmetric pattern. When the side length of the square pattern is even, its center is the common vertex of the $4$ middle cells; when the side length is odd, the pattern has a central cell, and the center of the pattern is also the center of that central cell. A pattern of side length $1$ is obviously an $8$-symmetric pattern.

Mr. Zhang proves two theorems to the students.

• Theorem $1$: A square pattern is a $4$-symmetric pattern if and only if it is both a $180$-degree symmetric pattern and an axis-symmetric pattern.
• Theorem $2$: A square pattern is an $8$-symmetric pattern if and only if it is both a $90$-degree symmetric pattern and an axis-symmetric pattern.

Finally, it is practice time. Mr. Zhang asks the students to find various symmetric patterns that appear inside a large square pattern. Please write a program to do this. Given a $01$ matrix, output the maximum side length of a contiguous square submatrix that satisfies, respectively, $8$-symmetry, $90$-degree symmetry, $4$-symmetry, $180$-degree symmetry, and axis symmetry. A contiguous square submatrix means a submatrix chosen by selecting several adjacent rows and columns, representing a small pattern appearing in the large pattern.

Input Format

The first line contains a positive integer $n$, the side length of the large square pattern. Then follow $n$ lines, each a $01$ string of length $n$.

Output Format

Output one line containing $5$ natural numbers separated by spaces, representing the maximum side length of a contiguous square submatrix appearing in the input that is, respectively, $8$-symmetric, $90$-degree symmetric, $4$-symmetric, $180$-degree symmetric, and axis-symmetric.

5
11100
11000
10111
11000
11100

2 2 3 3 5

Hint

Explanation of the Sample

The large pattern has a horizontal axis of symmetry. There is a $2\times 2$ $8$-symmetric pattern in the upper-left corner. The rightmost $3$ columns of the middle $3$ rows form a $4$-symmetric pattern.

Constraints

For $100\%$ of the testdata, $5\leq n\leq 500$.

Translated by ChatGPT 5