题目描述

为了寻找传说中的宝藏，小明走进了一个迷宫，我们用一个 $r$ 行 $c$ 列的矩阵来描述这个迷宫，矩阵的每个位置表示一个方块区域：

• 字符 . 表示可以通过的方格。
• 字符 # 表示不能通过的方格。
• 在迷宫中有 $k$ 个机关，第 $i$ 个机关工作方式为：
  • 每当小明走上第 $r_i$ 行，$c_i$ 列的格子时，位于第 $R_i$ 行，$C_i$ 列的格子改变状态（如果这个格子此时可以通过，此后就变为不能通过；如果此时不能通过，此后可以通过。最左上角的格子是第 $1$ 行第 $1$ 列）。

现给出当前小明的位置，宝藏的位置，迷宫中每个格子的状态，以及所有机关的描述，问小明至少还要走多少步才能拿到宝藏（不能走出迷宫的边界，在开始时刻，小明和宝藏所在的位置都是可以通过的，机关不会出现在起点和终点，也不会影响这两个格子）。

输入格式

输入数据的第 $1$ 行是两个整数：$r$ 和 $c$。

输入数据的第 $2$ 行到第 $r+1$ 行，每行是一个长度为 $c$ 的字符串，描述迷宫的当前状态：. 表示此时可以通过的格子，# 表示此时不能通过的格子，S 表示起点，T 表示宝藏的位置。

输入数据的第 $r+2$ 行是一个整数 $k$，表示机关的数目。接下来有 $k$ 行，每一行包含 $4$ 个整数 $r_i,c_i,R_i,C_i$，用来描述一个机关。

输出格式

输出一个整数：小明最少需要走多少步才能拿到宝藏。测试数据保证可以找到宝藏。

5 5
S.#..
#####
..#..
##.#.
...#T
6
1 5 4 2
1 4 3 3
5 1 3 3
1 4 4 5
1 2 1 3
1 5 2 1

22

提示

数据范围及约定

对于全部数据，$5 \le r, c \le 30$，$0 \le k \le 10$，$1 \le r_i,R_i\le r$，$1 \le c_i,C_i \le c$。