该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

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

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

输出格式

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

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

567

数据规模

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