Alternate Escape

Time Limit : 8 sec, Memory Limit : 262144 KB

Alternate Escape

アリスハウス

AliceとBobはボードゲームで遊んでいる. このボードゲームは, HW 列のマス目が書かれた盤面と1つのコマを使って遊ぶ. このゲームでは,盤面の左上のマスを1行1列目として,下方向に行を,右方向に列を数える.

マス同士が隣接する辺と,マスが盤面の外側と接する辺には壁を置けるようになっていて,ゲームの開始時にはそれぞれの辺について壁の有無が指定されている.また,ゲームの開始時には,コマが盤面のマスのいずれか1箇所に置かれている.

AliceとBobは交互に手番をこなすことでゲームを進める. ゲームはAliceの手番から始まる. Aliceの目的は,コマを盤面の外まで動かして,迷路から脱出させることである. Aliceが1手でできる行動は,コマを今ある位置のマスから,上下左右に隣接するマスのうち,間の辺に壁がない方向のいずれかに移動させることである. コマの今あるマスが盤面の外側に接していて,間の辺に壁がない場合,そこからコマを脱出させることができる.

一方,Bobの目的は,コマの脱出を妨害することである. Bobの手番では,壁の有無を反転させるか,何もせずに手番を終えるかを選ぶことができる. 壁の有無を反転させることを選んだ場合,盤面のすべてのマスの辺について,壁の有無が反転する.

盤面の初期状態と,コマの初期位置が与えられるので,AliceとBobの両者が最適な行動をとったときに,Aliceがコマを盤面から脱出させられるか判定せよ. ただし,Aliceの手番においてコマが4方向とも壁で囲まれてしまった場合は脱出できないとみなす.

Input

入力は40個以下のデータセットからなる. それぞれのデータセットは次の形式で与えられる.

H W R C
 Horz1,1 Horz1,2 ... Horz1,W
Vert1,1 Vert1,2 ... Vert1,W+1
...
VertH,1 VertH,2 ... VertH,W+1
 HorzH+1,1 HorzH+1,2 ... HorzH+1,W

1行目には4つの整数 H, W (1 ≤ H, W ≤ 500), R, C (1 ≤ RH, 1 ≤ CW) が与えられる. これらは盤面が HW 列のマス目からなり,コマの初期位置が RC 列目であることを表す.

続く 2H + 1 行には盤面の初期状態が与えられる.

2i 行目 (1 ≤ iH + 1) は,W個の整数 Horzi,1, Horzi,2, ..., Horzi,Wを含む. Horzi,jは,ij 列目のマスの上側の辺に壁が有るとき1で,無いとき0である. ただし,HorzH+1,jは, Hj 列目のマスの下側の辺における壁の有無を表す.

2i + 1 行目 (1 ≤ iH) は,W + 1 個の整数 Verti,1, Verti,2, ..., Verti,W+1を含む. Verti,jは, ij 列目のマスの左側の辺に壁が有るとき1で,無いとき0である. ただし,Verti,W+1は, iW 列目のマスの右側の辺における壁の有無を表す.

入力の終わりは,4つのゼロからなる1行で示される.

Output

それぞれのデータセットについて,Aliceがコマを盤面から脱出させられる場合は"Yes",できない場合は"No"と1行に出力せよ.

Sample Input

3 3 2 2
 1 1 1
0 0 0 0
 1 1 1
0 0 0 0
 1 1 1
0 0 0 0
 1 1 1
3 3 2 2
 1 0 1
1 0 1 1
 1 0 0
0 0 0 0
 0 0 1
1 1 0 1
 1 0 1
1 3 1 1
 1 1 1
1 0 0 1
 1 0 1
2 2 1 1
 1 0
1 0 0
 0 0
0 0 0
 0 0
0 0 0 0

Output for Sample Input

Yes
No
Yes
No

Hint

1つ目のデータセットではAliceは次のように動くことでコマを脱出させられる。

  1. 初期状態
  2. Aliceがコマを左に動かす
  3. Bobは脱出を阻止するために壁を反転させる
  4. Aliceがコマを上に動かす

Bobが次の手番で壁の有無を反転させてもさせなくても、 Aliceは次の手番でコマを脱出させられる。


Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2015, 2015-06-14
http://acm-icpc.aitea.net/