Rescue in the Haunted Maze

Last night, little erriyue had a horrible nightmare. In his dream, he and his girlfriend were trapped in a large maze, but in different parts of it. Even more terrifying, two ghosts haunted the maze, and their only goal was to kill any human they encountered. Now, erriyue wants to know if he can reach his girlfriend before the ghosts catch either of them.

Both erriyue and his girlfriend can move in 4 directions (up, down, left, right). In each second, erriyue is very agile and can move up to 3 steps, while his girlfriend can move 1 step per second. The ghosts are evil: every second they divide and occupy all grid cells within 2 steps (in terms of Manhattan distance) from each ghost’s current position. Note that the ghosts’ expansion happens first at the beginning of every second and continues recursively: newly spawned ghosts can also divide in subsequent seconds. If erriyue or his girlfriend ever enters a cell that is already occupied by a ghost, they die immediately.

Your task is to determine whether there exists a safe meeting cell in the maze where erriyue and his girlfriend can meet, i.e. both can reach that cell at some second t (possibly by delaying their arrival) and the cell is still ghost-free at that time. Formally, if we define the arrival time for erriyue at cell \( (r,c) \) as \(T_e(r,c)\) and for his girlfriend as \(T_g(r,c)\), then a meeting cell is safe if:

[ \max{T_e(r,c), T_g(r,c)} < T_{ghost}(r,c), ]

where \(T_{ghost}(r,c)\) is the time at which ghosts occupy cell \( (r,c) \). Since ghosts expand by occupying every cell within 2 Manhattan steps every second, we have for any cell \( (r,c) \) and a ghost starting at \( (r_g,c_g) \):

[ T_{ghost}(r,c) = \min\left{\left\lceil \frac{|r - r_g|+|c-c_g|}{2} \right\rceil\right} \quad \text{over the two ghosts}, ]

The players must also navigate the maze’s obstacles. The maze is given as an \(n \times m\) grid where each cell is either open (denoted by '.') or a wall (denoted by '#'). Players can only traverse open cells.

Input Format:

• The first line contains two integers \(n\) and \(m\) (the number of rows and columns of the maze).
• The next \(n\) lines each contain a string of length \(m\), representing the maze. A '.' indicates an open cell and a '#' indicates a wall.
• The following line contains two integers, representing erriyue's starting coordinates (row and column, 1-indexed).
• The next line contains two integers, representing his girlfriend's starting coordinates (1-indexed).
• The next two lines each contain two integers, representing the starting coordinates (1-indexed) of the two ghosts.

Output Format:

Output a single line with YES if there exists a safe meeting cell where they can meet; otherwise, output NO.

Note: You may assume that the players can delay their arrival if needed (i.e. they are not forced to move at maximum speed every second) as long as they follow the movement rules.

inputFormat

The input begins with two space-separated integers \(n\) and \(m\) (maze dimensions). Followed by \(n\) lines, each containing a string of length \(m\) representing the maze grid (with '.' for open and '#' for wall). Then:

• One line with two integers: erriyue's starting row and column (1-indexed).
• One line with two integers: his girlfriend's starting row and column (1-indexed).
• Two lines, each with two integers representing the starting row and column (1-indexed) of a ghost.

outputFormat

Output a single line: YES if there exists a safe meeting cell where erriyue can meet his girlfriend before the ghosts occupy it; otherwise, output NO.

sample

3 3
...
...
...
1 1
3 3
1 3
3 1

NO