题目描述

有一个农场，每个区域组成一个 $n \times n$ 的矩阵，其中第 $i$ 行第 $j$ 列的区域收益为 $a_{i,j}$。

ws.hcl 想买下一部分区域，而为了便于管理，这片区域必须是一个长方形。定义子矩形 $(x_1, x_2, y_1, y_2)$（$1 \le x_1 \le x_2, 1 \le y_1 \le y_2$）为以 $(x_1, y_1)$ 为左上角、$(x_2, y_2)$ 为右下角组成的矩形区域。

买下某片区域后需要用围栏将该区域围起来，定义子矩形 $(x_1, x_2, y_1, y_2)$ 的围栏长度为：

$$C(x_1, x_2, y_1, y_2) = 2 \times (x_2 - x_1 + 1) + 2 \times (y_2 - y_1 + 1)$$

围住该子矩形所需的围栏数量即为周长。

定义子矩形 $(x_1, x_2, y_1, y_2)$ 的总收益为：

$$S(x_1, x_2, y_1, y_2) = \sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} a_{i,j}$$

ws.hcl 追求性价比，因此你需要帮他找出收益总收益和周长的最大比值，即：

$$\max_{1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le n} \frac{S(x_1, x_2, y_1, y_2)}{C(x_1, x_2, y_1, y_2)}$$

在此基础上，你还需给出一个方案，这样 ws.hcl 才能理解你的想法并做出最优的选择。

---

输入格式

从文件 farm.in 中读入数据。

• 第一行输入一个整数 $n$，表示矩阵的边长。
• 接下来 $n$ 行，每行 $n$ 个整数，其中第 $i$ 行第 $j$ 列的数字表示 $a_{i,j}$。

---

输出格式

输出到文件 farm.out 中。

对于每组数据：

• 第一行一个浮点数，表示总收益和周长的最大比值。
• 第二行输出两个空格隔开的整数 $y_1, y_2$；
• 第三行输出两个空格隔开的整数 $x_1, x_2$， 表示其中一个方案为 $(x_1, x_2, y_1, y_2)$。若有多个方案符合条件，任选输出即可。

你的答案的绝对或相对误差不能超过 $10^{-7}$。你的子矩形被认为是正确，当且仅当其误差 $\le 10^{-7}$。

形式化地说，设你的答案为 $a$，正确答案为 $b$，允许的误差范围内为：

$$|a - b| \le 10^{-7}$$

---

样例 #1

样例输入 #1

2
100 100
1 1

样例输出 #1

33.3333333333333
1 1
2 1

---

样例 #2

见附加文件 farm2.in 和 farm2.ans。

---

样例 #3

见附加文件 farm3.in 和 farm3.ans。

---

数据范围

对于所有数据：

• $1 \le n \le 500$
• $|a_{i,j}| \le 10^9$

每个测试点的具体限制如下表所示：

测试点编号	$n \le$
1 ~ 5	100
6 ~ 10	200
11 ~ 15	300
16 ~ 20	400
21 ~ 25	500