Minimum Sum Subrectangle

You are given a 2D grid (matrix) consisting of n rows and m columns of integers. Your task is to find the contiguous subrectangle (submatrix) that has the minimum possible sum. The answer should be returned as five integers: the 1-indexed row and column of the top‐left corner, the 1-indexed row and column of the bottom‐right corner, and the minimal sum of the subrectangle.

If there are several subrectangles that achieve the minimum sum, output any one of them.

Note: A subrectangle is defined by choosing two rows and two columns (the boundaries) such that it includes all the cells within these boundaries.

inputFormat

The first line contains two space-separated integers n and m, denoting the number of rows and columns respectively.

The following n lines each contain m space-separated integers representing the grid.

Input is read from standard input (stdin).

outputFormat

Output five space-separated integers: r1, c1, r2, c2 and the minimal sum, where (r1,c1) is the top-left corner and (r2,c2) is the bottom-right corner of the subrectangle. The positions use 1-based indexing.

Output should be written to standard output (stdout).

4 5
1 2 3 4 5
6 7 8 9 10
-1 -2 -3 -4 -5
5 4 3 2 1

3 1 3 5 -15