时空限制

1S/512M

题目描述

给定一个 $n \times n$ 的二维数组 $A$。

你的任务是找出二维数组 $A$ 中三个位置相邻且在同一直线上的数的最大乘积。

“同一直线”包括水平、竖直以及两条对角线方向（左上到右下，右上到左下）。

格式

输入格式

第一行包含一个整数 $n$，表示二维数组 $A$ 的大小。

接下来 $n$ 行，每行包含 $n$ 个非负整数。其中第 $i$ 行的第 $j$ 个数表示二维数组中的元素 $A_{i,j}$。

输出格式

输出一个整数，表示能找到的最大乘积。

样例

样例输入 #1

4
8 2 8 1
4 7 3 5
5 6 9 2
1 4 2 9

样例输出 #1

567

数据规模

对于 $100\%$ 的数据，$3 \leq n \leq 1000$，$0 \leq A_{i,j} \leq 1000$。