농장의 작은 수확 시연

문제

한 농장의 작물 구역은 N개의 행과 M개의 열로 나뉜 직사각형 격자이다. 행 번호는 위에서 아래로 1번부터 N번까지, 열 번호는 왼쪽에서 오른쪽으로 1번부터 M번까지 붙어 있다. 각 칸에는 오늘 수확할 수 있는 작물의 수가 적혀 있다. 작물의 수가 0인 칸도 정상적인 구역이며, 그 칸을 시연 구역에 포함하는 데에는 문제가 없다. 농장에서는 방문객에게 수확 과정을 보여 주기 위해 작은 시연 구역 하나를 고르려 한다. 시연용 울타리는 정확히 두 행과 두 열에 걸친 네 칸을 둘러싸는 모양이다. 따라서 시연 구역은 서로 이웃한 두 행과 서로 이웃한 두 열을 선택했을 때 만들어지는 2행 2열의 정사각형이어야 한다. 떨어진 칸을 모으거나 농장의 경계 밖으로 울타리를 내밀 수는 없다. 시연 구역을 정하면 그 안의 네 칸에서 오늘 수확할 수 있는 작물을 모두 수확한다. 시연 구역의 수확량은 네 칸에 적힌 수의 합이며, 구역 밖의 작물은 수확량에 포함하지 않는다. 농장 관리인은 가능한 시연 구역 중 수확량이 가장 큰 구역을 고르려 한다. 작물의 종류나 칸 사이의 이동 거리처럼 입력에 없는 조건은 고려하지 않는다. 수확량이 가장 큰 구역이 여러 개라면 왼쪽 위 칸의 행 번호가 가장 작은 구역을 고른다. 행 번호도 같다면 왼쪽 위 칸의 열 번호가 가장 작은 구역을 고른다. 선택한 구역의 왼쪽 위 칸 위치와 수확량을 구한다. N과 M은 모두 2 이상이므로 시연 구역을 고를 수 없는 경우는 없다.

입력

첫째 줄에 정수 N과 M이 주어진다. 2 ≤ N, M ≤ 200이다.
다음 N개 줄에는 각 행의 작물 수가 M개씩 주어진다. i번째 행의 j번째 값 A_ij는 정수이며 0 ≤ A_ij ≤ 9이다.

출력

선택한 시연 구역의 왼쪽 위 칸의 행 번호, 열 번호, 수확량을 공백으로 구분하여 한 줄에 출력한다.

3 4
1 2 0 4
3 1 5 0
0 2 4 3

2 2 12

2 3
0 0 0
0 0 0

1 1 0

2 2
9 1
2 8

1 1 20

출처: Devin.KR 자체 제작