Mirko 在一个山丘小镇上找到了一份邮递员的工作。这个小镇可以用一个 $N \times N$ 的矩阵来表示。每个格子仅包含以下内容之一：用 'K' 表示的房屋、用 'P' 表示的邮局，或用 '.' 表示的牧场。此外，每个格子都被分配了一个海拔高度。

每天早晨，Mirko 都要向镇上的所有房屋投递信件。他从用 'P' 表示的格子出发，该格子代表镇上唯一的邮局。Mirko 只能移动到相邻的格子，允许水平、垂直和对角线方向移动。一旦他投递完最后一封信，他就必须返回邮局。

Mirko 根本不知道他的工作会有多累。我们将 Mirko 在投递信件（并返回邮局）过程中访问过的格子的最高海拔与最低海拔之差定义为他的疲劳度。请帮助他确定投递完所有信件并返回邮局所需的最小可能疲劳度。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 50$）。

接下来的 $N$ 行表示矩阵中对应行的格子。字符 'P' 将恰好出现一次，而字符 'K' 将至少出现一次。

接下来的 $N$ 行，每行包含 $N$ 个正整数，表示对应矩阵行中格子的海拔高度。这些数值均小于 $1\,000\,000$。

输出格式

在单行中输出一个整数，表示最小可能的疲劳度。

样例

输入样例 1

2
P.
.K
2 1
3 2

输出样例 1

0

输入样例 2

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

输出样例 2

2

输入样例 3

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

输出样例 3

5

说明

第一个样例说明：从邮局出发，Mirko 可以直接移动到有房子的格子，投递信件，然后返回邮局。由于邮局所在的格子和房子所在的格子海拔相同，Mirko 的疲劳度为 $0$。