Alice and Bob live in a country consisting of $N$ islands, numbered from $0$ to $N-1$. Some islands are connected by bridges. The bridges are bidirectional, but each can only accommodate one person at a time. Some bridges have become dangerous due to disrepair and can be used at most twice.

Alice wants to travel between island $a_1$ and $a_2$ exactly $a_n$ times (a round trip from $a_1$ to $a_2$ and back to $a_1$ counts as one trip). At the same time, Bob wants to travel between island $b_1$ and $b_2$ exactly $b_n$ times. During this process, all dangerous bridges can be used at most twice, while other bridges can be used an unlimited number of times. Can Alice and Bob fulfill their wishes?

Input

The input contains multiple test cases.

Each test case starts with a line containing 7 space-separated integers: $N$, $a_1$, $a_2$, $a_n$, $b_1$, $b_2$, $b_n$.

This is followed by an $N \times N$ symmetric matrix consisting of uppercase letters. The entry in the $i$-th row and $j$-th column describes the connection between island $i$ and island $j$. 'O' indicates that the bridge is dangerous, 'N' indicates a normal bridge, and 'X' indicates no bridge.

Output

For each test case, output "Yes" if they can fulfill their wishes, otherwise output "No".

Examples

Input 1

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

Output 1

Yes
No

Constraints

• $4 \le N \le 50$
• $0 \le a_1, a_2, b_1, b_2 \le N-1$
• $1 \le a_n, b_n \le 50$