There is a H times W rectangle divided into unit cells. The rows of cells are numbered 0 to H-1 from top to bottom, and the columns are numbered 0 to W-1 from left to right. The corners of cells are called lattice points. By definition, there are (H+1)*(W+1) lattice points in our rectangle.
Each of the four edges of each cell is painted white. Additionally, in some cells exactly one of the two diagonals is painted white. In the remaining cells no diagonal is painted white yet. Later, you are going to paint exactly one of the diagonals white in each of these cells.
Once you are done painting the diagonals, your next goal will be to color each of the lattice points using one of three available colors: red, green, or blue. There is only one constraint: adjacent lattice points are not allowed to share the same color.
Two lattice points are called adjacent if they are connected by a white line segment. (In other words, consecutive corners of a cell are always adjacent, opposite corners of a cell are adjacent if and only if they are connected by a painted diagonal, and no other pairs of lattice points are adjacent.)
Obviously, you need to paint the missing diagonals in such a way that there will be a valid coloring of lattice points, if possible.
You are given a
If it is impossible to fill in the missing diagonals in such a way that there will be a valid coloring of all lattice points, return an empty