P6083 [JSOI2015] symmetry

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. ```plain 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. ```plain 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.

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 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.

#### 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