题目描述

小 C 勇闯 CFS 校园。校园里有一处不为人知的小公园。

这个小公园可以看做 $n$ 行 $m$ 列的网格图。

每一格都有各自不同的状态。

1. . 是一个可以通行的格子。
2. # 是一个障碍格子，不可以通行。
3. S 是小 C 现在所在的位置。这个格子也可以通行。
4. T 是小 C 想要去的位置。这个格子也可以通行。

小 C 每一次移动到相邻的格子，都会消耗 $1$ 的体力值。如果体力值变成了 $0$，他将无法移动。

但是网格里一共有 $k$ 件药品。第 $i$ 件药品在第 $x_i$ 行第 $y_i$ 列上。到达第 $x_i$ 行第 $y_i$ 列时，可以将体力值直接修改为 $z_i$。也就是小 C 不一定要吃这件药品。吃过的药品就会消失。

请你告诉小 C 是否存在一种方式使他能够顺利到达 T 点。

特殊的，体力值到达 $0$ 时恰好在 T 点，也算到达了 T 点。

小 C 的初始体力值为 $0$。

输入格式

第一行两个正整数 $n,m$ 表示小公园的规模。保证 $1\leq n,m\leq 200$。

接下来 $n$ 行每行 $m$ 个字符，如题目描述表示每一格的状态。保证 S 和 T 至多出现一次，保证地图只由 S、T、.、# 构成。

接下来一行一个正整数 $k$ 表示药品数量。保证 $1\leq k\leq 300$

接下来 $k$ 行每行 $3$ 个正整数 $x_i,y_i,z_i$ 表示药品所在位置以及吃下之后的新体力值。保证 $1\leq x_i\leq n$，$1\leq y_i\leq m$，$1\leq z_i\leq 10^9$，保证两种药品不会出现在一个位置上，保证药品不会出现在 # 的格子上。

输出格式

一行一个字符串 YES 或 NO 表示小 C 能否到达 T 点。若能输出 YES 否则输出 NO。

样例 #1

样例输入 #1

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

样例输出 #1

YES

样例 #2

样例输入 #2

2 2
S.
T.
1
1 2 4

样例输出 #2

NO

样例 #3

样例输入 #3

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

样例输出 #3

YES

提示

本题开启捆绑测试。同一子任务只有输出全部正确才可得到该子任务的分数。

子任务 1：30 分。满足 $1\leq n,m\leq 200$，$k=1$。

子任务 2：30 分。满足 $1\leq n,m\leq 200$，$1\leq k\leq 200$。

子任务 3：40 分。满足 $1\leq n,m\leq 200$，$1\leq k\leq 300$。