BaoBao 在他的左口袋里发现了一个 $n$ 行 $m$ 列的网格，其中第 $i$ 行第 $j$ 列的单元格（记作 $(i, j)$）包含一个箭头（指向向上、向下、向左或向右）和一个整数 $a_{i,j}$。

BaoBao 决定玩一个关于这个网格的游戏。他首先选择一个单元格作为初始单元格并将其标记。在标记了一个单元格（假设 BaoBao 刚刚标记了单元格 $(i, j)$）之后，BaoBao 将根据该单元格 $(i, j)$ 中的箭头和整数继续标记下一个单元格。

• 如果单元格 $(i, j)$ 中的箭头指向向上，BaoBao 将继续标记单元格 $(i - a_{i,j}, j)$（如果该单元格存在）。
• 如果单元格 $(i, j)$ 中的箭头指向向下，BaoBao 将继续标记单元格 $(i + a_{i,j}, j)$（如果该单元格存在）。
• 如果单元格 $(i, j)$ 中的箭头指向向左，BaoBao 将继续标记单元格 $(i, j - a_{i,j})$（如果该单元格存在）。
• 如果单元格 $(i, j)$ 中的箭头指向向右，BaoBao 将继续标记单元格 $(i, j + a_{i,j})$（如果该单元格存在）。

如果 BaoBao 决定标记的单元格不存在，或者该单元格已经被标记过，游戏结束。

BaoBao 想知道他是否可以选择一个合适的初始单元格，使得他在游戏结束前能够恰好标记网格中的每一个单元格各一次。请帮他找到答案。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$ ($1 \le n \times m \le 10^5$)，表示网格的行数和列数。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$（$|s_i| = m, s_{i,j} \in \{'u', 'd', 'l', 'r'\}$），其中 $s_{i,j}$ 表示单元格 $(i, j)$ 中箭头的方向。

• 如果 $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$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($1 \le a_{i,j} \le \max(n, m)$)，其中 $a_{i,j}$ 表示单元格 $(i, j)$ 中的整数。

保证所有测试数据的 $n \times m$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行。如果 BaoBao 能找到一个合适的初始单元格，输出 “Yes”（不含引号），否则输出 “No”（不含引号）。

样例

输入 1

2
2 3
rdd
url
2 1 1
1 1 2
2 2
rr
rr
1 1
1 1

输出 1

Yes
No

说明

对于第一个样例测试数据，BaoBao 可以选择单元格 $(1, 2)$ 作为初始单元格，这样他可以按以下顺序恰好标记所有单元格各一次：$(1, 2), (2, 2), (2, 3), (2, 1), (1, 1), (1, 3)$。

对于第二个样例测试数据，无论选择哪个单元格作为初始单元格，BaoBao 最多只能标记 2 个单元格。