1340: #2239. 「CQOI2014」危桥

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Alice 和 Bob 居住在一个由 NNN 座岛屿组成的国家,岛屿被编号为 000N−1N-1N1。某些岛屿之间有桥相连,桥上的道路是双向的,但一次只能供一人通行。其中一些桥由于年久失修成为危桥,最多只能通行两次。

Alice 希望在岛屿 a1a_1a1a2a_2a2 之间往返 ana_nan 次(从 a1a1a1a2a2a2 再从 a2a2a2a1a1a1 算一次往返)。同时,Bob 希望在岛屿 b1b_1b1b2b_2b2 之间往返 bnb_nbn 次。这个过程中,所有危桥最多通行两次,其余的桥可以无限次通行。请问 Alice 和 Bob 能完成他们的愿望吗?

输入格式

本题有多组测试数据。

每组数据第一行包含七个空格隔开的整数,分别为NNNa1a_1a1a2a_2a2ana_nanb1b_1b1b2b_2b2bnb_nbn
接下来是一个 NNNNNN 列的对称矩阵,由大写字母组成。矩阵的 iiijjj 列描述编号 i−1i-1i1j−1j-1j1 的岛屿间的连接情况,若为 “O” 则表示有危桥相连:为 “N” 表示有普通的桥相连:为 “X” 表示没有桥相连。

输出格式

对于每组测试数据输出一行,如果他们都能完成愿望输出 “Yes”,否则输出 “No”(不含引号)。

样例

样例输入

4 0 1 1 2 3 1
XOXX
OXOX
XOXO
XXOX
4 0 2 1 1 3 2
XNXO
NXOX
XOXO
OXOX

样例输出

Yes
No

数据范围与提示

对于所有数据,4≤N<50, 0≤a1,a2,b1,b2≤N−1, 1≤an,bn≤504 \leq N<50,\ 0 \leq a_1, a_2, b_1, b_2 \leq N-1,\ 1 \leq a_n, b_n \leq 504N<50, 0a1,a2,b1,b2N1, 1an,bn50