퍼즐 조각 맞추기

어린 Barborka는 직소 퍼즐 맞추는 법을 배우기 시작했다. 처음에는 조각이 15개뿐인 작은 퍼즐로 시작했다. 아빠도 함께 퍼즐을 맞추려 하는데, 난이도를 높이려고 모든 조각을 뒤집어 그림이 보이지 않게 해 두었다. 이제 아빠는 그림을 보지 못한 채로 퍼즐을 맞추려 한다. 보통은 답이 존재하지만, Barborka가 비슷한 다른 퍼즐의 조각을 섞어 놓지는 않았는지 확신할 수 없다. 아빠를 도와, 퍼즐 조각들의 정보를 읽고 그 조각들을 주어진 가로·세로 크기의 직사각형으로 맞출 수 있는지 판정하는 프로그램을 작성하여라.

입력은 여러 개의 블록으로 이루어진다. 마지막 블록을 제외한 각 블록은 하나의 퍼즐을 나타낸다.

각 블록의 첫 줄에는 두 정수 $n$과 $m$ ($0 < n, m \le 6$)이 공백 하나로 구분되어 주어진다. 각각 퍼즐의 행 수와 열 수를 뜻한다.

이어지는 $n \times m$개의 줄에는 각 조각의 정보가 주어진다. 모든 조각은 가로 3센티미터, 세로 4센티미터인 직사각형이며, 각 변의 가운데에 돌기(볼록)나 홈(오목)이 있을 수 있다. 조각의 각 변은 다음 중 정확히 하나에 해당한다(그림 참고).

• 돌기도 홈도 없는 평평한 변 — 평평한 변은 완성된 직사각형의 바깥 테두리에만 놓을 수 있다.
• 변의 가운데에 돌기가 하나 있는 경우.
• 변의 가운데에 홈이 하나 있는 경우.

보통의 퍼즐처럼, 두 조각은 맞닿는 변에서 한쪽에 돌기가 있고 다른 쪽에 그에 맞는 홈이 있을 때에만 나란히 놓을 수 있다. 평평한 변은 F, 돌기가 있는 변은 O, 홈이 있는 변은 I로 나타낸다. 각 조각은 위, 오른쪽, 아래, 왼쪽 변을 이 순서대로 나타내는 네 글자로 설명된다. 조각은 설명된 방향 그대로만 사용할 수 있으며, 회전할 수 없다.

블록과 블록 사이는 빈 줄로 구분된다. 마지막 블록은 0 0(공백으로 구분된 두 개의 0)만 있는 한 줄이며, 이는 입력의 끝을 나타낸다.

마지막 블록을 제외한 각 입력 블록마다 한 줄씩 출력한다. 해당 블록의 조각들을 요청된 직사각형으로 올바르게 맞출 수 있으면 YES를, 그렇지 않으면 NO를 출력한다. 입력을 끝내는 0 0 블록에 대해서는 아무것도 출력하지 않는다.