CF463C.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).

加尔加里嫉妒他的朋友凯萨在上一题中赢得了游戏，他想证明自己是个天才。

他有一个 $n \times n$ 的国际象棋棋盘，棋盘的每个格子上都写有一个数字。加尔加里希望在棋盘上放置两个主教（象），使得不存在任何一个格子同时被这两个主教攻击。考虑一个写有数字 $x$ 的格子：若该格子被其中一个主教攻击，则加尔加里将获得 $x$ 美元。请告诉加尔加里，应如何在棋盘上放置这两个主教，才能使他获得的钱数最多。

我们规定：若一个格子与某个主教位于同一条对角线上，则该格子被该主教攻击（主教所在的格子本身也被视为被其攻击）。

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

第一行包含一个整数 $n$（$2 \leq n \leq 2000$）。接下来的 $n$ 行，每行包含 $n$ 个整数 $a_{ij}$（$0 \leq a_{ij} \leq 10^9$），表示棋盘的描述。

On the first line print the maximal number of dollars Gargari will get. On the next line print four integers: _x_1, _y_1, _x_2, _y_2 (1 ≤ _x_1, _y_1, _x_2, _y_2 ≤ n), where x__i is the number of the row where the i-th bishop should be placed, y__i 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.

第一行输出 Gargari 能获得的最大美元数。
第二行输出四个整数：$x_1,\ y_1,\ x_2,\ y_2$（其中 $1 \le x_1, y_1, x_2, y_2 \le n$），分别表示第 $i$ 个主教应放置的行号 $x_i$ 和列号 $y_i$。行号从上到下编号为 $1$ 到 $n$，列号从左到右编号为 $1$ 到 $n$。

若存在多个最优解，输出任意一个即可。