题目描述

$N$ 行 $M$ 列のグリッドがあります． あなたはグリッドの各マスに $0$ 以上 $2^K-1$ 以下の整数を書き込み，以下の条件を満たしたいです．

• 左上のマスを出発し，右または下に隣接するマスへの移動を繰り返して，右下のマスへと至るパスを考える． ここで，通ったマス (始点終点を含む) に書かれた整数の総 $\mathrm{XOR}$ が $0$ になるパスを，よいパスと呼ぶことにする．
• よいパスはちょうど $1$ つだけ存在し，それは文字列 $S$ が表すパスである． 文字列 $S$ が表すパスとは，各 $i$ ($1\ \leq\ i\ \leq\ N+M-2$) について，$i$ 回目の移動の際，$S$ の $i$ 文字目が R なら右，D なら下に進むようなパスである．

条件を満たす整数の書き込み方が存在するかどうか判定してください．

$1$ つの入力ファイルにつき，$T$ 個のテストケースを解いてください．

ビット単位 $\mathrm{XOR}$ 演算とは 非負整数 $A,\ B$ のビット単位 $\mathrm{XOR}$ 、$A\ \oplus\ B$ は、以下のように定義されます。

• $A\ \oplus\ B$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $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,\ p_3,\ \dots,\ p_k$ の順番によらないことが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる．

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

各ケースは以下の形式で与えられる．

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

输出格式

各ケースに対し，条件を満たす整数の書き込み方が存在する場合は Yes を，存在しないならば No を出力せよ． 出力中の各文字は英大文字・小文字のいずれでもよい．

题目大意

请在一个 $N \times M$ 的方格表中，为每个方格填入一个 $0$ 到 $2^K-1$ 的整数，使得：

• 考虑从左上角到右下角，只向右或向下移动到相邻方格的一条路径。一条这样的路径被称为好的，当且仅当这条路径上所有方格中的数的异或和是 $0$。
• 方格表中应恰存在一条好的路径。它是用一个给定的字符串 $S$ 表示的。对每个 $1 \le i \le N+M-2$，路径的第 $i$ 次移动是向右，当且仅当 $S$ 的第 $i$ 个字符是 R；是向下，当且仅当 $S$ 的第 $i$ 个字符是 D。

判断这样的方格表是否存在。$T$ 组数据。

数据范围：

• $1 \le T \le 100$
• $2 \le N,M \le 30$
• $1 \le K \le 30$
• $S$ 是一个恰包含 $N-1$ 个 D 和 $M-1$ 个 R 的字符串。

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-1$ 個の D と $M-1$ 個の R からなる文字列
• 入力される数はすべて整数

Sample Explanation 1

例えば $1$ ケース目については，以下のようなグリッドを作れば良いです． 11 00