Submit
 

D : Draw Puzzle

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem D: Draw Puzzle

Problem

以下のようなパズルゲームがある。
プレイヤーには、グリッド状になっている1枚のボードと、ボードに設置するためのパネルが与えられる。
パネルには以下の4種類が存在し、それぞれ、左から順にa、b、c、dと名前が付けられている。
また、パネルに描かれている線は、道の断片を表している。

ボードには縦に3個、横にN個、合計3×N個のマスが並んでおり、マスには赤いマスと白いマスの2種類が存在する。
このパズルの目的は、4種類のパネルを上手くボードに配置し、パネルに描かれている道の断片をつなぎ合わせて左側の壁から右側の壁への道を作ることである。
道を作ることができた場合のみゲームクリアとなる。
左側の壁について、どの格子点を出発点にするかはプレイヤーの自由である。
右側の壁での到達点についても同様である。

例えば、図1にあるようなボードとパネルの組み合わせならば、図2にあるような回答例が存在することになる。

(図1)

(図2)

  • パネルを全て使い切る必要はない。
  • パネルを回転させて設置することはできない。
  • 赤いマスにパネルを設置することはできない。
  • 同じマスに複数のパネルを重ねて設置することはできない。

入力として、ボードの状態と、プレイヤーに渡されるパネル4種類のそれぞれの枚数が与えられる。
あなたの仕事は、その入力から、そのパズルゲームがクリア可能かどうかを判定するプログラムを書くことである。
上手にパネルを設置することでクリア可能ならば"Yes"と出力せよ。
反対に、どのようにパネルを設置してもクリアできない場合は、"No"と出力せよ。

Input

N 
string1 
string2 
string3
a b c d

1行目には、ボードの横幅を表す整数Nが与えられる。
2,3,4行目には、ボードの情報を表す長さNの文字列string1,2,3が与えられる。
これらはそれぞれボードの上から1,2,3段目の状態を表す。
これらの文字列は大文字ファルファベットの'O'と'X'のみを含んでおり、'O'は白いマスを表し、'X'は赤いマスを表す。
5行目には、空白区切りで4つの整数a,b,c,dが与えられる。
これらはそれぞれプレイヤーが最初に持っているパネルa,b,c,dの枚数を表す。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ N ≤ 30
  • N = | string1,2,3 |
  • 0 ≤ a,b,c,d ≤ 10

Output

"Yes"または"No"を1行に出力せよ。

Sample Input 1

7
OOOOXOO
OXOOOXO
XOXOOOX
3 3 2 2

Sample Output 1

Yes

Sample Input 2

7
OOOOOOX
XOOOOOX
XOOOOOO
3 3 1 0

Sample Output 2

No