题目描述

我们有一个 $N$ 行 $M$ 列的网格。你想要在网格中的每个方格里写一个介于 $0$ 和 $2^K-1$ 之间的整数，以满足以下条件。

• 考虑从左上角方格开始、一直向右或向下移动到相邻方格，直到到达右下角方格的路径。如果路径上经过的方格上整数的$\\mathrm{XOR}$（即异或运算）为 0，则该路径被称为好路径。
• 存在且只存在一条好路径，该路径由字符串 $S$ 表示。字符串 $S$ 表示的路径是这样的：对于每个 $i$（$1 \\leq i \\leq N+M-2$），如果 $S$ 的第 $i$ 个字符为 R，则第 $i$ 步向右移动；如果 $S$ 的第 $i$ 个字符为 D，则第 $i$ 步向下移动。

确定是否存在一种方法来写入整数满足上述条件。

对于每个输入文件，解决 $T$ 个测试用例。

什么是位运算的 $\\mathrm{XOR}$？

非负整数 $A$ 和 $B$ 的位运算 $\\mathrm{XOR}$，用 $A \\oplus B$ 表示，定义如下。

• 当以二进制形式表示 $A \\oplus B$ 时，第 $k$ 位（$k \\geq 0$）为 1，当且仅当 $A$ 和 $B$ 的第 $k$ 位中只有一个为 1，否则为 0。

例如，$3 \\oplus 5 = 6$（二进制表示：$011 \\oplus 101 = 110$）。 通常，$k$ 个非负整数 $p_1, p_2, p_3, \\dots, p_k$ 的位运算 $\\mathrm{XOR}$ 被定义为 $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$，可以证明该运算与 $p_1, p_2, \ldots, p_k$ 的顺序无关。

约束条件

• $1 \\leq T \\leq 100$
• $2 \\leq N,M \\leq 30$
• $1 \\leq K \\leq 30$
• $S$ 是一个包含恰好 $N-1$ 个 D 和 $M-1$ 个 R 的字符串。
• 输入中的所有数字都是整数。

输入

从标准输入中按以下格式给出输入：

$T$ $case_1$ $case_2$ $\\vdots$ $case_T$

每个测试用例的格式如下：

$N$ $M$ $K$ $S$

输出

对于每个测试用例，如果存在一种满足条件的整数写入方法，则输出 Yes，否则输出 No。输出中的每个字符都可以是大写或小写字母。

样例输入 1

4
2 2 1
RD
4 3 1
RDDDR
15 20 18
DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR
20 15 7
DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD

样例输出 1

Yes
No
Yes
No

例如，对于第一个测试用例，你可以构建以下网格：

11
00