Description
After two months of dieting, Yanami Anna decided to reward herself. She signed up for a local district's big eater competition. This competition is different from regular big eater contests, with rules as follows:
There's a food map with N rows and M columns. Each spot on the map has a number showing the points for eating that food. You can only pick a square or rectangle area to eat from. The person with the highest score can win the championship prize.
Yanami hopes you can help her find the area with the highest total score. She needs your help to tell her where this area is by giving her top-left and bottom-right corner points: (X1 , Y1 ), (X2 , Y2). Don't worry if it seems like too much food - she'll be fine.
If there's more than one answer:
- Pick the one with the smallest X1 .
- If X1 is the same, choose the smaller Y1 .
- If both X1 and Y1 are the same, choose the smaller X2.
- If X1 , Y1 , and X2 are all the same, choose the smaller Y2.
In the sample test case, the green area represents the region with the highest total score.
The top-left and bottom-right corner points: (X1 , Y1 ), (X2 , Y2) are shown in the figure below.
Input
The first line contains N and M, representing the number of rows and columns of the map.
The following N lines represent the map, each containing M integers.
Constraints
- 1 ≤ N, M ≤ 150
- 1 ≤ i ≤ N
- 1 ≤ j ≤ M
- -109 ≤ Ci,j ≤ 109
Subtasks
- Testcases 1 ~ 3: 1 ≤ N, M ≤ 10, -105 ≤ Ci,j ≤ 105
- Testcases 4 ~ 6: 1 ≤ N, M ≤ 100
- Testcases 7 ~ 8: No additional restrictions.
Output
The first line contains the top-left corner point: (X1 , Y1 ).
The second line contains the bottom-right corner point: (X2 , Y2).
Please remember to print "\n" at the end.