Gargari and Bishops
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).
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.
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.
from sys import stdin
input = stdin.buffer.readline
I = lambda : list(map(int, input().split()))
mat = []
for _ in range(int(input())):
    mat.append(I())
n = len(mat)

def sumDiag(mat):
    diag_sum = []
    diag_sum2 = []
    n = len(mat)
    for i in range(n):
        s = 0
        for j in range(0, n - i):
            s += mat[j][j + i]
        diag_sum.append(s)
        if i != 0:
            s = 0
            for j in range(0, n - i):
                s += mat[j + i][j]
            diag_sum2.append(s)
    return diag_sum2[::-1] + diag_sum

def antiDiag(mat):

    def mirror(mat):
        for i in range(len(mat)):
            for j in range(len(mat[0]) // 2):
                t = mat[i][j]
                mat[i][j] = mat[i][len(mat[0]) - 1 - j]
                mat[i][len(mat[0]) - 1 - j] = t
        return mat
    mat = mirror(mat)
    out = sumDiag(mat)
    mirror(mat)
    return out[::-1]
d1 = sumDiag(mat)
d2 = antiDiag(mat)

def ret(i, j):
    return d1[n - 1 - (i - j)] + d2[i + j] - mat[i][j]
m1 = 0
m2 = 0
best1 = (1, 1)
best2 = (1, 2)
for i in range(n):
    for j in range(n):
        if (i + j) % 2 == 0 and m1 < ret(i, j):
            m1 = ret(i, j)
            best1 = (i + 1, j + 1)
        elif (i + j) % 2 == 1 and m2 < ret(i, j):
            m2 = ret(i, j)
            best2 = (i + 1, j + 1)
print(m1 + m2)
print(' '.join(map(str, [best1[0], best1[1], best2[0], best2[1]])))
from sys import stdin
input = stdin.buffer.readline
I = lambda : list(map(int, input().split()))
mat = []
for _ in range(int(input())):
    mat.append(I())
n = len(mat)

def sumDiag(mat):
    diag_sum = []
    diag_sum2 = []
    n = len(mat)
    for i in range(n):
        s = 0
        for j in range(0, n - i):
            s += mat[j][j + i]
        diag_sum.append(s)
        if i != 0:
            s = 0
            for j in range(0, n - i):
                s += mat[j + i][j]
            diag_sum2.append(s)
    return diag_sum2[::-1] + diag_sum

def antiDiag(mat):

    def mirror(mat):
        for i in range(len(mat)):
            for j in range(len(mat[0]) // 2):
                t = mat[i][j]
                mat[i][j] = mat[i][len(mat[0]) - 1 - j]
                mat[i][len(mat[0]) - 1 - j] = t
        return mat
    mat = mirror(mat)
    out = sumDiag(mat)
    mirror(mat)
    return out[::-1]
d1 = sumDiag(mat)
d2 = antiDiag(mat)

def ret(i, j):
    return d1[n - 1 - (i - j)] + d2[i + j] - mat[i][j]
m1 = 0
m2 = 0
best1 = (1, 1)
best2 = (1, 2)
for i in range(n):
    for j in range(n):
        if (i + j) % 2 == 0 and m1 < ret(i, j):
            m1 = ret(i, j)
            best1 = (i + 1, j + 1)
        elif (i + j) % 2 == 1 and m2 < ret(i, j):
            m2 = ret(i, j)
            best2 = (i + 1, j + 1)
print(m1 + m2)
print(' '.join(map(str, [best1[0], best1[1], best2[0], best2[1]])))
def freq(arr):
    d = {}
    for i in arr:
        d[i] = d.get(i, 0) + 1
    return d

def solve():
    rdiag = [0 for i in range(2 * n - 1)]
    ldiag = [0 for i in range(2 * n - 1)]
    for i in range(n):
        for j in range(n):
            rdiag[i + j] += arr[i][j]
            ldiag[n - 1 - i + j] += arr[i][j]
    wmx = 0
    wpos = (1, 1)
    bmx = 0
    bpos = (1, 2)
    for i in range(n):
        for j in range(n):
            val = rdiag[i + j] + ldiag[n - 1 - i + j] - arr[i][j]
            if (i + j) % 2 == 0:
                if wmx < val:
                    wmx = val
                    wpos = (i + 1, j + 1)
            elif bmx < val:
                bmx = val
                bpos = (i + 1, j + 1)
    print(wmx + bmx)
    return f'{wpos[0]} {wpos[1]} {bpos[0]} {bpos[1]}'
from sys import stdin
input = stdin.buffer.readline

def main():
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    rdiag = [0 for i in range(2 * n - 1)]
    ldiag = [0 for i in range(2 * n - 1)]
    for i in range(n):
        for j in range(n):
            rdiag[i + j] += arr[i][j]
            ldiag[n - 1 - i + j] += arr[i][j]
    wmx = 0
    wpos = 1
    wpos1 = 1
    bmx = 0
    bpos = 1
    bpos1 = 2
    for i in range(n):
        for j in range(n):
            val = rdiag[i + j] + ldiag[n - 1 - i + j] - arr[i][j]
            if (i + j) % 2 == 0:
                if wmx < val:
                    wmx = val
                    wpos = i + 1
                    wpos1 = j + 1
            elif bmx < val:
                bmx = val
                bpos = i + 1
                bpos1 = j + 1
    print(wmx + bmx)
    print(wpos, wpos1, bpos, bpos1)
if __name__ == '__main__':
    main()
''