索菲亚皇后被困在一个神秘的 $n$ 行 $m$ 列的棋盘上。棋盘上包含她的起点方格（标记为 S）和终点方格（标记为 E）。不幸的是，通往终点的道路并不容易——一些方格被阻挡了（标记为 #），而其他方格是空闲的（标记为 .）。

但棋盘上还隐藏着神奇的传送门！某些 $1$ 到 $9$ 之间的数字在棋盘上恰好出现两次。如果皇后落在写有数字的方格上，她可以传送到棋盘上具有相同数字的另一个方格，而无需为通过传送门而消耗额外的移动步数。皇后在穿过传送门后，如果不额外花费 $1$ 步移动，就不能继续沿相同方向移动。

皇后的移动方式与国际象棋中的皇后类似——在一步移动中，她可以移动到与她处于同一对角线、同一行或同一列的任何方格，但前提是她与该方格之间（包括该次移动的起点和终点）没有被阻挡的方格。

求出并输出皇后从起点方格到达终点方格所需的最少移动步数，如果无法到达，则输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$），分别表示棋盘的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个字符 $c_{ij}$，表示棋盘的描述。棋盘上的每个字符将是 S、E、$1$ 到 $9$ 之间的数字、. 或 # 之一。

输出格式

在第一行也是唯一一行中，输出一个整数，表示皇后到达终点方格所需的最少移动步数。

子任务

样例

输入样例 1

4 4
S..1
####
1.#E
....

输出样例 1

4

输入样例 2

3 3
S..
.#.
..E

输出样例 2

2

输入样例 3

5 4
S.21
####
2##1
###.
E..#

输出样例 3

4

说明

索菲亚皇后在第一步移动中将移动到第 1 行的数字 1（注意 S 和 1 之间没有被阻挡的方格，因此这一步移动确实是可行的）。然后她将传送到矩阵中的第二个数字 1，并再进行 3 步移动到达终点方格。通过这些移动，她确实完成了从起点到终点方格所需的最少移动步数。