题目描述

小明在挑战一个大迷宫，迷宫用一个 $R\times C$ 的字符矩阵来表示。字符 S 表示小明所在的位置，字符 E 表示终点所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。小明在 $1$ 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

为了帮助小明，红红指定了 $m$ 个特殊位置，第 $i$ 个特殊位置在第 $x_i$ 行、第 $y_i$ 列。如果小明走到了一个特殊位置，那么他在 $1$ 个单位时间内可以从当前的位置走到它上、下、左、右、左上、左下、右上、右下八个方向上的任意一个位置，但不能走出地图边界。

求小明最快多少个单位时间能走到终点，如果无法走到终点，输出 -1。

输入格式

第一行包含了两个用空格分开的正整数 $R$ 和 $C$，表示地图是一个 $R\times C$ 的矩阵。

接下来的 $R$ 行描述了地图的具体内容，每一行包含了 $C$ 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

接下来一行是一个整数 $m$。

接下来的 $m$ 行，每行为空格隔开的两个整数，第 $i$ 行是 $x_i,y_i$。

输出格式

输出一行，为一个整数，即小明最快多少个单位时间能走到终点，如果无法走到终点，输出 -1。

3 4
.S..
###.
E...
0

7

样例解释 1

七步分别为：右右下下左左左。

3 4
.S..
###.
E...
1
2 4

6

样例解释 2

六步分别为：右、右、下、左下、左、左。

3 4
.S.#
###.
E...
2
1 3
2 4

5

样例解释 3

五步分别为：右、右下、左下、左、左。

数据规模与约定

对于 $100\%$ 的数据，$1 \le R,C \le 1000$，$0\le m\le 5000$，$1\le x_1\le R$，$1\le y_i\le C$。

• 子任务 1（30 分）：保证地图中没有 #，且 $m=0$。
• 子任务 2（30 分）：保证 $m=0$。
• 子任务 3（40 分）：没有特殊限制。