文字列 $X$ に対して次の規則を定めます。

規則

• 文字列 $X$ は L、R、U、D からなる。
• 文字列 $X$ において L と R はそれぞれ隣接せず、 U と D もそれぞれ隣接しない。
  • より厳密には、 $S$ の任意の連続部分文字列は LR、RL、UD、DU のいずれにも一致しない。

正の整数 $N$ と長さ $M$ の文字列 $S$ が与えられます。ここで $S$ は規則を満たします。

次の要件をすべて満たす壁と床のみからなる縦 $(2N + 1)$ マス、横 $(2N + 1)$ マスの $(2N + 1) \times (2N + 1)$ マスからなる迷路が存在するか判定してください。存在する場合、そのような迷路を $1$ つ出力してください。

ここで、迷路の最も左上のマスをマス $(0, 0)$ として、マス $(0, 0)$ から下に $i$ マス、右に $j$ マス移動したマスをマス $(i, j)$ と表します。

要件

1. 迷路のスタート地点はマス $(1, 1)$ 、ゴール地点はマス $(2N - 1, 2N - 1)$ である。
2. 迷路の外周はすべて壁である。より厳密には、 $0$ 以上 $2N$ 以下の任意の整数 $x$ について、マス $(0, x)$、マス $(2N, x)$、マス $(x, 0)$、マス $(x, 2N)$ はすべて壁のマスである。
3. $i$ と $j$ がどちらも奇数であるマス $(i, j)$ は床のマスであり、 $i$ と $j$ がどちらも偶数であるマス $(i, j)$ は壁のマスである。
4. 迷路は文字列 $S$ で表される手順に従ってスタート地点からゴール地点まで床のみを通って移動することができる。より厳密には、スタート地点から文字列 $S$ で表される手順に従って $M$ 回移動したとき、移動経路上のマスがすべて床のマスであり、かつ移動を終えたときにいるマスがゴール地点である。ここで $k$ 回目の移動の内容を下記の通り表す。
   • $S$ の $k$ 文字目が L のとき、左に $1$ マス移動することを表す。すなわち、移動前のマスをマス $(i, j)$ とするとき、移動後のマスはマス $(i, j − 1)$ である。
   • $S$ の $k$ 文字目が R のとき、右に $1$ マス移動することを表す。すなわち、移動前のマスをマス $(i, j)$ とするとき、移動後のマスはマス $(i, j + 1)$ である。
   • $S$ の $k$ 文字目が U のとき、上に $1$ マス移動することを表す。すなわち、移動前のマスをマス $(i, j)$ とするとき、移動後のマスはマス $(i - 1, j)$ である。
   • $S$ の $k$ 文字目が D のとき、下に $1$ マス移動することを表す。すなわち、移動前のマスをマス $(i, j)$ とするとき、移動後のマスはマス $(i + 1, j)$ である。
5. 迷路はループするような構造を持たない。より厳密には、あるマス $(i, j)$ からマス $(i, j)$ と異なるマス $(i^\prime, j^\prime)$ へ床のマスのみを通って移動する手順を表す、規則を満たす文字列は高々 $1$ つしか存在しない。ここで、文字列で表される移動の手順は要件4.と同様である。
6. 迷路はスタート地点から到達することのできない床は存在しない。より厳密には、すべての床のマスについて、スタート地点から床のマスのみを通って移動する手順を表す、規則を満たす文字列 $T$ が存在する。ここで、移動する方法は要件4.と同様の方法である。

例えば、$N = 3, M = 8, S =$ RRDDRRDD のとき、次のような迷路は要件をすべて満たすため、正解となります。
このとき、スタート地点であるマス $(1, 1)$ から $S$ の表す通りに移動すると青いマスを通ることになり、ゴール地点であるマス $(5, 5)$ に辿り着くことができます。

同様に、次のような迷路も正解となります。

不正解となる例をいくつか示します。

次の迷路は赤く塗られたマス $(5, 1)$ について、 $5$ と $1$ がどちらも奇数であるにもかかわらず壁のマスとなっているため、要件の $3$ 番目の項を満たしていません。よって不正解となります。

次の迷路は $S$ で表される手順で移動したとき、壁のマスであるマス $(3, 4)$ を通ってしまうため、要件の $4$ 番目の項を満たしていません。よって不正解となります。

次の迷路は赤く塗られたマスにおいてループを構成しているため、要件の $5$ 番目の項を満たしていません。具体的にはマス $(1, 3)$ からマス $(3, 5)$ に移動する手順を表す規則を満たす文字列として RRDD と DDRR の $2$ 種類が存在します。よって不正解となります。

次の迷路はスタート地点からマス $(3, 1)$ に移動することができないため、要件の $6$ 番目の項を満たしません。よって不正解となります。

Hard (100点)

• $2 \le N \le 1500$
• $1 \le M \le 2 \times N^2$
• $S$ は規則を満たす長さ $M$ の文字列
• $N, M$ は整数

Easy (50点)

• Hardの制約に以下の制約を追加
• 要件をすべて満たす迷路が必ず存在する
• $3 \le N \le 5$
• $N$ は奇数
• $M = 2 \times (N^2 - 1)$

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

要件をすべて満たす迷路が存在しない場合、 No と出力せよ。

要件をすべて満たす迷路が存在する場合、 Yes と出力し、改行せよ。その後、そのような迷路を次の形式で $1$ つ出力せよ。入出力例も参考にすること。

ここで、 $L_i$ は長さ $(2N + 1)$ の # と . からなる文字列である必要があり、 $L_i$ の $j$ 文字目が # のときマス $(i, j)$ が壁のマスであることを、 . のときマス $(i, j)$ が床のマスであることを表す。

なお、要件をすべて満たす迷路が複数存在する場合、どれを出力しても構わない。