Maximum Sum Submatrix

You are given a 2D matrix of size \(N \times M\) filled with integers and an integer \(k\). Your task is to find the \(k \times k\) submatrix with the maximum sum. If there are multiple submatrices that yield the same maximum sum, return the one that appears first when scanning from top-left to bottom-right. If \(k\) is greater than either \(N\) or \(M\), output -1.

Input Constraints:

• \(1 \leq N, M \leq 1000\)
• \(-10^9 \leq matrix[i][j] \leq 10^9\)
• \(1 \leq k \leq max(N, M)\)

Explanation: A submatrix is a contiguous block of the original matrix. The sum of a \(k \times k\) submatrix is the sum of all its elements. You are required to print the resulting submatrix if one exists, else print -1.

inputFormat

The first line of input contains three integers \(N\), \(M\), and \(k\) separated by spaces. The next \(N\) lines each contain \(M\) integers representing the rows of the matrix.

outputFormat

If a \(k \times k\) submatrix exists, output \(k\) lines with \(k\) space-separated integers each representing the submatrix having the maximum sum. If \(k\) is greater than \(N\) or \(M\), output -1.

## sample

2 2 2
1 2
3 4

1 2
3 4

</p>