T434252 「YAC Round 7」魔理沙骑着扫帚飞


魔理沙喜欢在幻想乡的天空中骑着扫帚自由翱翔。 幻想乡是一个 $n$ 行 $m$ 列的方格图。 对于每个位置 $(i, j)$ 都有一个方向 和一个元素 $a_{i, j}$。 魔理沙决定玩一个游戏。 他首先需要选择一个初始位置，然后将其标记。 标记完了这个位置后，魔理沙需要根据这个位置的方向和元素 $a_{i, j}$ 移动并继续进行标记。 具体如下： - 如果位于 $(i, j)$ 位置的方向为 **向上**，那么魔理沙需要移动到 $(i - a{i, j}, j)$ 的位置并继续标记，前提是位置存在。 - 如果位于 $(i, j)$ 位置的方向为 **向下**，那么魔理沙需要移动到 $(i + a{i, j}, j)$ 的位置并继续标记，前提是位置存在。 - 如果位于 $(i, j)$ 位置的方向为 **向左**，那么魔理沙需要移动到 $(i, j - a_{i, j})$ 的位置并继续标记，前提是位置存在。 、 - 如果位于 $(i, j)$ 位置的方向为 **向右**，那么魔理沙需要移动到 $(i, j + a_{i, j})$ 的位置并继续标记，前提是位置存在。 如果魔理沙需要继续标记的位置不存在，或者位置已经被标记了，那么游戏结束。 魔理沙想知道，她是否可以找到一个初始的位置，并且可以从这个位置开始标记完方格图中所有的位置。 请你帮魔理沙判断一下是否存在答案。

**有多组测试数据** 第一行包含一个整数 $T$，表示数据组数。 对于每组数据： 第一行包含两个整数 $n$ 和 $m$ $\;$ ($1 \le n \times m \le 10^5$)，表示方格图的大小。 接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。 $s_{i, j}$ 表示位置 $(i,j)$ 上的方向 $\;$ ($s_{i, j} \in \{ 'u', 'd', 'l', 'r' \}$)。 具体地： - 如果 $s_{i, j} = 'u'$，那么位置 $(i, j)$ 上的方向为 **向上**。 - 如果 $s_{i, j} = 'd'$，那么位置 $(i, j)$ 上的方向为 **向下**。 - 如果 $s_{i, j} = 'l'$，那么位置 $(i, j)$ 上的方向为 **向左**。 - 如果 $s_{i, j} = 'r'$，那么位置 $(i, j)$ 上的方向为 **向右**。 接下来 $n$ 行，每行 $m$ 个整数 $a_{i, 1}, a_{i, 2} , \ldots , a_{i, m}$ $1 \le a_{i,j} \le \max(n,m)$，$a_{i,j}$ 表示位置 $(i, j)$ 上的元素。 保证所有的 $n \times m$ 之和不超过 $10^6$ 。

对于每组测试数据： 如果存在一个初始位置可以标记到所有位置，那么输出 `Yes`；否则，输出 `No` 。

第一组样例中，魔理沙可以选择初始位置为 $(1, 2)$，然后她可以依次标记 $(1, 2), (2, 2), (2, 3), (2, 1), (1, 1), (1, 3)$，即所有位置全部标记。 第二组样例中，魔理沙最多只能标记掉两个位置，没有一个初始位置可以满足标记所有位置。