Gargari is jealous that his friend Caisa won the game from the previous problem. He wants to prove that he is a genius.

He has a n × n chessboard. Each cell of the chessboard has a number written on it. Gargari wants to place two bishops on the chessboard in such a way that there is no cell that is attacked by both of them. Consider a cell with number x written on it, if this cell is attacked by one of the bishops Gargari will get x dollars for it. Tell Gargari, how to place bishops on the chessboard to get maximum amount of money.

We assume a cell is attacked by a bishop, if the cell is located on the same diagonal with the bishop (the cell, where the bishop is, also considered attacked by it).

Input

The first line contains a single integer n (2 ≤ n ≤ 2000). Each of the next n lines contains n integers aij (0 ≤ aij ≤ 109) — description of the chessboard.

Output

On the first line print the maximal number of dollars Gargari will get. On the next line print four integers: x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n), where xi is the number of the row where the i-th bishop should be placed, yi is the number of the column where the i-th bishop should be placed. Consider rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left to right.

If there are several optimal solutions, you can print any of them.

Examples

Input

4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1


Output

12
2 2 3 2
from sys import stdin

def max_num(a,b,c, n):
	maxa = 0
	maxb = 0
	A = 1
	B = 1
	C = 1
	D = 2
	for i in range(n):
		for j in range(n):
			if (i + j) % 2 == 0:
				if b[i][j]+c[i][j]-a[i][j] > maxa:
					maxa = b[i][j]+c[i][j]-a[i][j]
					A = i + 1
					B = j + 1
			else:
				if b[i][j]+c[i][j]-a[i][j] > maxb:
					maxb = b[i][j]+c[i][j]-a[i][j]
					C = i + 1
					D = j + 1
	return [maxa + maxb, A, B, C, D]


n = int(stdin.readline())
a = []
for i in range(n):
	a.append(list(map(int, stdin.readline().split())))
b = [[0 for i in range(n)] for j in range(n)]
c = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	for j in range(n - i):
		b[0][i] += a[j][i + j]
for i in range(1, n):
	for j in range(n - i):
		b[i][0] += a[i + j][j]
for i in range(1, n):
	for j in range(1, n):
		z = min(i, j)
		b[i][j] += b[i - z][j - z]
for i in range(n):
	for j in range(i + 1):
		c[0][i] += a[i - j][j]
for i in range(1, n):
	for j in range(n - i):
		c[i][-1] += a[i + j][n - j - 1]
for i in range(1, n):
	for j in range(n - 1):
		c[i][j] += c[i - 1][j + 1]
a1 = max_num(a,b,c, n)
print(a1[0])
ans=''
ans+=str(a1[1])
ans+=' '
ans+=str(a1[2])
ans+=' '
ans+=str(a1[3])
ans+=' '
ans+=str(a1[4])
print(ans)