Alternate Escape

ID: 2787

Type: Default

8000ms

268MiB

Alice House

Alice and Bob are playing board games. This board game is played using a board with squares in rows H and columns and one frame. In this game, the upper left square of the board is set as the 1st row and 1st column, and the rows are counted downward and the columns are counted to the right.

Walls can be placed on the sides where the squares are adjacent to each other and on the sides where the squares are in contact with the outside of the board, and the presence or absence of walls is specified for each side at the start of the game. Also, at the beginning of the game, the piece is placed in one of the squares on the board.

Alice and Bob take turns alternately to advance the game. The game starts with Alice's turn. The purpose of Alice is to move the top out of the board to escape from the maze. The action that Alice can do with one hand is to move the piece from the square at the current position to one of the squares adjacent to the top, bottom, left, and right, in the direction where there is no wall on the side between them. If the existing square of the piece is in contact with the outside of the board and there is no wall on the side between them, the piece can be escaped from there.

On the other hand, Bob's purpose is to prevent the escape of the top. In Bob's turn, you can choose to flip the presence or absence of the wall or finish the turn without doing anything. If you choose to invert the presence or absence of walls, the presence or absence of walls will be inverted for all sides of the squares on the board.

Since the initial state of the board and the initial position of the top are given, determine whether Alice can escape the top from the board when both Alice and Bob take the optimum action. However, if Alice's turn is surrounded by walls in all four directions, it is considered that she cannot escape.

Input

The input consists of 40 or less datasets. Each dataset is given in the following format.

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

The first line gives four integers H, W (1 ≤ H, W ≤ 500), R, C (1 ≤ R ≤ H, 1 ≤ C ≤ W). These indicate that the board consists of squares in rows H and columns W, and the initial position of the frame is rows R and columns C.

The following 2H + 1 line gives the initial state of the board.

Line 2i (1 ≤ i ≤ H + 1) contains W integers Horzi, 1, Horzi, 2, ..., Horzi, W. Horzi, j is 1 when there is a wall on the upper side of the square in row i and column j, and 0 when there is no wall. However, HorzH + 1, j indicates the presence or absence of a wall on the lower side of the square in the H row and j column.

The 2i + 1st line (1 ≤ i ≤ H) contains W + 1 integer Verti, 1, Verti, 2, ..., Verti, W + 1. Verti, j is 1 when there is a wall on the left side of the cell in the i-th row and j-th column, and 0 when there is no wall. However, Verti and W + 1 indicate the presence or absence of a wall on the right side of the cell in the i-row and W-th column.

The end of the input is indicated by a single line of four zeros.

Output

For each dataset, output "Yes" if Alice can get the frame out of the board, or "No" if not.

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 Ten 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Output for Sample Input

Yes No Yes No

Hint

In the first dataset, Alice can escape the piece by moving as follows.

Initial state
Alice moves the top to the left
Bob flips the wall to prevent escape
Alice moves the top up

Whether or not Bob flips the wall on his next turn, Alice can escape the piece on his next turn.

Example

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

Yes No Yes No

inputFormat

Input

The input consists of 40 or less datasets. Each dataset is given in the following format.

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

The following 2H + 1 line gives the initial state of the board.

The end of the input is indicated by a single line of four zeros.

outputFormat

Output

For each dataset, output "Yes" if Alice can get the frame out of the board, or "No" if not.

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 Ten 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Output for Sample Input

Yes No Yes No

Hint

In the first dataset, Alice can escape the piece by moving as follows.

Initial state
Alice moves the top to the left
Bob flips the wall to prevent escape
Alice moves the top up

Whether or not Bob flips the wall on his next turn, Alice can escape the piece on his next turn.

Example

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

Yes No Yes No

样例

Yes
No
Yes
No

</p>

#D3359. Alternate Escape

Alternate Escape