密林の奥深くに位置するという Icpca 村は,相反する奇妙な伝承で有名である.
一説には,そこは具現化された幸福であるという.一説には,そこは身の毛もよだつ恐怖の要塞であるという.
数少ない情報源である老占者によれば,Icpca 村は長方形で,道路は格子状に整備されており,東西方向に n 本,南北方向に m 本の道路がそれぞれまっすぐに村を貫いているらしい.
なお,n と m はともに偶数である.
伝承の真相を探るため,n + m 人からなる調査チームが Icpca 村に派遣された.調査計画は以下の通りであった.
-
最初の n 人の調査員のうち i 人目は,東西方向の道路のうちの北から i 本目を,西端から東端に向かって歩く.
- 残る m 人の調査員のうち j 人目は,南北方向の道路のうちの西から j 本目を,北端から南端に向かって歩く.
調査員のうち何人かは,予定通りに Icpca 村から帰還した.しかしながら残りの調査員は,いまだに音信不通のままだ……
老占者の幻視によれば,Icpca 村の東西方向と南北方向の道路の交わる nm 個の交差点には,それぞれ石像がちょうど 1 体立っているという.
石像には美しい像と恐ろしい像の二種類があり,すべての像はそのどちらかである.
各調査員は正気度と呼ばれる値を持っており,Icpca 村に入る時点では,すべての調査員の正気度は 0 であった.
調査員の正気度は,美しい像のある交差点にさしかかると 1 増加する.また,恐ろしい像のある交差点にさしかかると 1 減少する.
恐ろしい像はとても恐ろしいので,途中で正気度が負になった場合,調査員はその場で動けなくなって,村に取り残されてしまう.
美しい像はとても美しいので,もし Icpca 村を出る時点で正気度が正なら,調査員は村から出るのを嫌がり,やはり村に取り残されてしまう.
どちらにも当てはまらない調査員,すなわち,途中で正気度が負にならず,村を出る時点で正気度が 0 であった調査員だけが,無事に村から帰還できる.
多くの遭難者を出しながらも調査は完了した.あなたは帰還した調査員のリストを持っている.
あなたの仕事はリストと矛盾しない美しい像と恐ろしい像の配置がありうるかを判定し,あるならそのひとつを求めることである.
入力は複数のデータセットからなる.
各データセットは次の形式で表される.
n m
A
B
n, m はそれぞれ,東西方向と南北方向の道路の本数を表す.
n, m は,正の偶数であり,100 を超えない.
A, B は それぞれ,各調査員が村を通過できたかを表す文字列である.
A は長さ n の,B は長さ m の,それぞれ 0 と 1 のみからなる文字列である.
A の i 文字目は,最初の n 人の調査員のうちの i 人目が村から帰還したかどうかの情報を表す.具体的には,0 のときは帰還していないことを,1 のときは帰還したことを表す.
同様に,B の j 文字目は,残る m 人の調査員のうちの j 人目が村から帰還したかどうかの情報を表す.
データセットの個数は 100 を超えない.
入力の終わりは,ゼロふたつからなる行で表される.
各データセットについて,リストと矛盾しない像の配置が存在しなければ 1 行に No を出力せよ.
存在すれば,1 行に Yes を出力し,続けて矛盾しない配置のひとつを n 行に出力せよ.
n 行のそれぞれは `+' と `−' からなる長さ m の文字列である.
i 番目の文字列の j 文字目の `+' は,北から i 本目の道路と西から j 番目の道路の交差点に美しい像があることを表し,`−' は恐ろしい像があることを表す.
リストと矛盾しない像の配置は複数あるかもしれないが,そのいずれを出力しても正答と判定される.