During his spare time, Bobo likes to play puzzle games a lot. His favorite one is The Witness, an acclaimed 2016 puzzle video game designed by Jonathan Blow. The Witness contains 9 principal types of puzzles and several hidden "environmental" puzzles, totaling an amount of 664 puzzles spread over the open world of the game. A player is invited to explore the world and to deduce the rules of various puzzles they encounter.
Among all types of puzzles, Bobo expertizes at a certain type called the "Black and White Squares" puzzle. This kind of puzzle is based on a rectangular grid and requires the player to connect a starting point to an end point with a simple grid path while splitting the grid cells of two different colors. The following are some real examples of this type of puzzle in-game together with one of their solutions. The starting point and the end point are marked with circles and a protruding semicircle from the grid, respectively.
Given an instance of the "Black and White Squares" puzzle such that all cells are either black or white, Bobo decides to leave you the challenge: can you provide a solution to the puzzle or assert there are none?
Formally, an instance of the "Black and White Squares" puzzle is described by the following:
- two positive integers $$$n,m$$$, representing the number of rows and columns of the rectangular grid. There are then $$$n\times m$$$ cells and $$$(n+1)\times (m+1)$$$ vertices in the grid. We label the vertex on the upper-left corner of the grid as $$$(0,0)$$$, the vertex on the lower-right corner of the grid as $$$(n,m)$$$, and the rest accordingly.
- An $$$n\times m$$$ two-dimensional array, representing the color of each cell. The color of each cell can only be either black or white.
- A starting point $$$(sx,sy)$$$ and an end point $$$(ex,ey)$$$ , each belonging to one of the vertices on the border of the grid. Here a vertex $$$(x,y)$$$ is on the border means at least one of the following is satisfied:
- $$$x=0$$$
- $$$x=n$$$
- $$$y=0$$$
- $$$y=m$$$
A solution to the "Black and White Squares" puzzle is described by a path $$$P=((x_1,y_1),(x_2,y_2),\dots,(x_{\ell},y_{\ell}))$$$ $$$(\ell\geq 2)$$$ satisfying the following properties:
- $$$(x_1,y_1)=(sx,sy)$$$ and $$$(x_{\ell},y_{\ell})=(ex,ey)$$$.
- For each $$$2\leq i\leq \ell$$$, it follows $$$(x_{i-1},y_{i-1})$$$ and $$$(x_{i},y_{i})$$$ are adjacent on the grid, i.e. one of the following is satisfied:
- $$$x_{i}=x_{i-1}$$$ and $$$| y_i-y_{i-1}|=1$$$
- $$$| x_{i}-x_{i-1}|=1$$$ and $$$y_i=y_{i-1}$$$
- $$$P$$$ is simple, i.e., for each $$$1\leq i \lt j\leq \ell$$$, either $$$x_i\neq x_j$$$ or $$$y_i\neq y_j$$$.
- Each region of the grid separated by the path contains only one color.
The first line contains two integers $$$n,m$$$ $$$(1\leq n,m\leq 40)$$$.
Then $$$n$$$ lines follow, the $$$i$$$-th line contains a string $$$s_i$$$ of length $$$m$$$ consisting of only '$$$B$$$' and '$$$W$$$', where the $$$j$$$-th character of $$$s_i$$$ represents the color of the cell on the $$$i$$$-th row and $$$j$$$-th column of the grid.
Then a line consisting of four integers $$$sx,sy,ex,ey$$$ $$$(0\leq sx,ex\leq n,0\leq sy,ey\leq m)$$$ follows, denoting the starting point and the end point. It is guaranteed that both the starting point and the end point are on the border of the grid and they don't coincide.
If there is no solution to the given "Black and White Squares" puzzle instance, output "NO" (without quotes) in a line.
Otherwise, output "YES" (without quotes) in the first line. Then output an integer $$$\ell$$$ $$$(\ell\geq 2)$$$, denoting the number of vertices contained in the solution path. Then on the $$$i$$$th of the next $$$\ell$$$ lines, output two integers $$$(x_i,y_i)$$$, denoting the $$$i$$$-th vertex in the solution path. Your answer will be considered correct if it meets the required conditions. If there are multiple solutions, you are allowed to output any of them.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes", and "Yes" will all be recognized as a positive response).
3 3 BBB BWB WWW 3 0 0 3
YES 9 3 0 2 0 2 1 1 1 1 2 2 2 2 3 1 3 0 3
1 1 W 0 0 1 1
YES 3 0 0 1 0 1 1
2 2 WB BW 0 0 2 2
NO
The first sample test describes the "Black and White Squares" puzzle instance in the fifth group of pictures in the statement.
For the second sample test, another valid solution path is $$$P=((0,0),(0,1),(1,1))$$$.
