Largest Uniform Subsquare Matrix

Given a square matrix consisting only of 0s and 1s, your task is to find the largest contiguous sub-square matrix in which all elements are identical. A sub-square matrix is defined by its side length, and its position is determined by the top-left corner (using 0-indexing).

If the matrix is empty, the answer should be 0 -1 -1 -1 (i.e. side length 0, and coordinates (-1, -1) with element -1).

Note: The output should consist of four integers separated by spaces: the side length, the row index of the top-left element, the column index of the top-left element, and the common element within that sub-square.

For example, consider the matrix:

1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

The largest uniform sub-square is of side length 2 starting at coordinate (0, 0) with all elements being 1. Thus the output should be:

2 0 0 1

The relation for building the dynamic programming solution can be described by the formula in LaTeX:

\[ \text{dp}(i,j) = \begin{cases} 1, & \text{if } i=0 \text{ or } j=0 \\ \min\{\text{dp}(i-1,j),\,\text{dp}(i,j-1),\,\text{dp}(i-1,j-1)\} + 1, & \text{if } matrix[i][j] = matrix[i-1][j] = matrix[i][j-1] = matrix[i-1][j-1] \\ 1, & \text{otherwise} \end{cases} \]

inputFormat

The input is given via standard input (stdin). The first line contains an integer n representing the size of the matrix. If n = 0, the matrix is empty. Otherwise, the next n lines each contain n space-separated integers (each being either 0 or 1) representing the rows of the matrix.

outputFormat

Output via standard output (stdout) a single line with four space-separated integers: the side length of the largest uniform sub-square, the row index and column index of its top-left element, and the element value of that sub-square.

## sample

4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

2 0 0 1