Puzzle

Little Barborka is learning to solve a jigsaw puzzle. She started with a small one made of 15 pieces. Her father wants to solve it too, but to make it more challenging he turned every piece face down so that he cannot see the pictures. Now he is trying to assemble the puzzle without seeing them. A solution should normally exist, but he is not sure whether Barborka mixed in pieces from another, similar puzzle. Help him: write a program that reads a description of a set of puzzle pieces and decides whether the pieces can be assembled into a rectangle with the given side lengths.

The input consists of several blocks of lines. Every block except the last describes one puzzle.

The first line of a block contains two integers $n$ and $m$ ($0 < n, m \le 6$), separated by one space. They are the number of rows and the number of columns of the puzzle, respectively.

The next $n \times m$ lines describe the individual pieces. Each piece is a rectangle 3 centimeters wide and 4 centimeters high that may have a jut or a cavity in the middle of each side. For every side of a piece exactly one of the following holds (see the picture):

• the side is flat, with no jut or cavity — a flat side may be used only on the outer edge of the assembled rectangle;
• there is one jut in the middle of the side;
• there is one cavity in the middle of the side.

As usual, two pieces may be placed side by side only if one has a jut and the other has a matching cavity on the touching sides. We denote a flat side by F, a side with a jut by O, and a side with a cavity by I. Each piece is described by four letters that give its top, right, bottom, and left side, in that order. The pieces may be used only exactly as described; they cannot be rotated.

Blocks are separated by an empty line. The last block is a single line containing 0 0 (two zeros separated by one space), which ends the input.

For every block of the input except the last, print one line: YES if the pieces of that block can be correctly assembled into the requested rectangle, and NO otherwise. Print nothing for the terminating 0 0 block.