该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

我们有一个 $N$ 行 $M$ 列的网格。你需要在每个格子中填入一个 $0$ 到 $2^K-1$ 之间的整数，满足以下条件：

• 考虑从左上角格子出发，每次向右或向下移动到相邻格子，最终到达右下角格子的路径。这样的路径被称为好路径当且仅当：
  • 路径经过的所有格子（包括起点和终点）中数字的按位异或（$\mathrm{XOR}$）总和为 $0$
• 在所有可能的路径中，有且只有一条好路径，这条路径由字符串 $S$ 表示：
  • $S$ 是一个长度为 $N+M-2$ 的字符串
  • 对于每个 $i$（$1 \leq i \leq N+M-2$）：
    • 如果 $S$ 的第 $i$ 个字符是 R，表示第 $i$ 步移动方向为右
    • 如果 $S$ 的第 $i$ 个字符是 D，表示第 $i$ 步移动方向为下

你需要判断是否存在满足条件的填数方案。

每个输入文件包含 $T$ 个测试用例。

按位异或说明

非负整数 $A$ 和 $B$ 的按位异或 $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_k$ 的按位异或定义为：

可以证明这个结果与计算顺序无关。

输入格式

• 第一行：整数 $T$ 表示测试用例数量
• 每个测试用例：
  • 第一行：三个整数 $N$, $M$, $K$
  • 第二行：字符串 $S$ 表示唯一的好路径

输出格式

对于每个测试用例：

• 如果存在满足条件的填数方案，输出 Yes
• 否则输出 No

示例

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

Yes
No
Yes
No

数据范围

• $1 \leq T \leq 100$
• $2 \leq N, M \leq 30$
• $1 \leq K \leq 30$
• $S$ 是由 $N+M-2$ 个字符组成的字符串，仅包含 R 和 D