您负责 ICPC（计算机程序评论协会）的安保工作。该协会位于一栋单层建筑内。其矩形楼层被划分为网格状的等大正方形区域。如果两个区域共享一条边，则称它们是相邻的。建筑内的一些区域被封锁了。被封锁区域的所有侧面都被墙壁围住，无法进入。所有其他区域之间没有墙壁，相邻区域通常可以互通。然而，一些相邻区域之间装有卷帘门，关闭这样的卷帘门会使得这两个区域之间无法直接通行。

最高机密研究正在建筑最外层的其中一个区域进行。该区域被称为最高机密区域。该建筑在最外层区域只有一个入口，这应该是进入建筑的唯一入口。然而，您注意到最外层区域的一扇窗户非常脆弱，可能会让入侵者进入建筑。

您必须保护最高机密免受入侵者的侵害。为此，您可能需要关闭一些卷帘门，使得从带有脆弱窗户的区域到最高机密区域的任何路径上，都至少需要破坏两个或更多的已关闭卷帘门。此外，从入口区域到最高机密区域必须至少存在一条没有关闭任何卷帘门的路径。

请编写一个程序，找出为保护最高机密所需关闭的卷帘门的最少数量。

输入格式

输入包含单个测试用例，格式如下：

$n \ m$ $s_1$ $\vdots$ $s_n$ $k$ $r_1 \ c_1 \ d_1$ $\vdots$ $r_k \ c_k \ d_k$

$n$ 和 $m$ 是 $2$ 到 $100$ 之间的整数（包含边界），表示建筑楼层有 $n$ 行 $m$ 列区域。第 $i$ 行第 $j$ 列的区域标识为 $(i, j)$。接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$，描述第 $i$ 行的区域。$s_i$ 的每个字符为 .、#、S、T 或 U 中的一个。如果 $s_i$ 的第 $j$ 个字符是 #，则区域 $(i, j)$ 被封锁且无法通行；否则，该区域是可通行的。$s_i$ 的第 $j$ 个字符为 S 表示区域 $(i, j)$ 是入口区域，T 表示最高机密区域，U 表示入侵者的入口点，即带有脆弱窗户的区域。S、T 和 U 在输入中作为最外层区域各出现且仅出现一次。最高机密区域可以通过可通行的区域从入口到达，且路径上没有关闭的卷帘门。

$k$ 是建筑内卷帘门的数量。接下来的 $k$ 行中，第 $i$ 行通过两个整数 $r_i$、$c_i$ 和一个字符 $d_i$ 描述一个卷帘门。$d_i$ 为 r 或 b。如果 $d_i$ 为 r，则满足 $1 \le r_i \le n$ 且 $1 \le c_i < m$，卷帘门安装在区域 $(r_i, c_i)$ 和 $(r_i, c_i + 1)$ 之间。如果 $d_i$ 为 b，则满足 $1 \le r_i < n$ 且 $1 \le c_i \le m$，卷帘门安装在区域 $(r_i, c_i)$ 和 $(r_i + 1, c_i)$ 之间。相同的 $r_i$、$c_i$ 和 $d_i$ 组合仅出现一次。每个卷帘门仅安装在两个未被封锁的相邻区域之间。

输出格式

输出一行，包含一个整数，表示为保护最高机密所需关闭的卷帘门的最少数量。如果无法做到，输出 $-1$。如果所有卷帘门打开时入侵者无法到达最高机密区域，输出 $0$。

样例

样例输入 1

3 3
S..
#..
U.T
7
1 2 b
1 3 b
2 2 b
2 2 r
2 3 b
3 1 r
3 2 r

样例输出 1

3

样例输入 2

2 2
ST
.U
4
1 1 r
1 1 b
1 2 b
2 1 r

样例输出 2

-1

样例输入 3

7 10
U.........
..........
###.......
..........
.......###
..........
S........T
18
4 4 r
5 4 r
6 7 r
7 7 r
3 4 b
3 5 b
3 6 b
3 7 b
3 8 b
3 9 b
3 10 b
5 1 b
5 2 b
5 3 b
5 4 b
5 5 b
5 6 b
5 7 b

样例输出 3

14

说明

样例 1 如下图所示。虚线表示卷帘门安装的位置。

图 C.1. 样例 1