多くのパズルの変種は、対応する元のジャンルより難しくなる傾向があります。しかし逆説的なことに、二文字加えるとより短くなる単語があるように、どんなジャンルもより簡単にする変種もあります。

— Freddie Hand

Grammy はパズルの達人です。今日は “Scrabble” パズルの変種である “Easy as Scrabble” を解いています。

パズルは $n\times m$ のグリッドからなります。各マスには大文字を一つ入れるか、空にしておきます。

パズルの外にはいくつかの手掛かりがあります。外側の手掛かりは、その方向から見て最初の空でないマスの文字を表します。また、一部のマスには x の印が付いている場合があり、そのマスが空でなければならないことを表します。

例えば、左の図は未解答のパズルを、右の図はそのパズルの一つの解を示しています。

Grammy はこのパズルの解を見つけたいと思っています。Grammy が解を見つけるのを手伝うか、解が存在しないと報告してください。

入力

最初の行には 2 個の整数 $n,m$（$1\le n,m\le1000$）が含まれ、グリッドの行数と列数を表します。

次の行には、点（.）、グリッドの上の手掛かりを表す $m$ 個の文字 $U_i$、そして点（.）が順に含まれます。

続く $n$ 行にはそれぞれ手掛かり $L_i$、$m$ 個の文字 $c_{ij}$、手掛かり $R_i$ が順に含まれ、グリッドの左の手掛かり、グリッドのマス、グリッドの右の手掛かりを表します。

次の行には、点（.）、グリッドの下の手掛かりを表す $m$ 個の文字 $D_i$、そして点（.）が順に含まれます。

各手掛かり $U_i,L_i,R_i,D_i$ は英大文字または点（.）です。各中央のマス $c_{ij}$ は x または点（.）です。

入力中のすべての点は、対応する位置が空であることを意味します。

出力

解が存在しない場合、一行に NO を出力してください。

そうでなければ、最初の行に YES を出力し、その後に各行が $m$ 文字からなる $n$ 行を出力して、パズルの一つの解を示してください。空のマスは点で表してください。解が複数ある場合、どれを出力しても構いません。

中央のマスに与えられた x の文字は、点に置き換える必要があることに注意してください。

手掛かりのマスを出力してはいけないことにも注意してください。

入出力例

入力 1

5 5
.CBA...
....x..
..x...C
A.....B
B..x..A
C......
.......

出力 1

YES
CBA..
A.B.C
.A.CB
BC.A.
..CBA

入力 2

1 2
....
Nx..
..O.

出力 2

NO