퍼즐 조각 맞추기2

정올이는 정사각형 모양의 퍼즐 조각 맞추기 놀이를 하고 있다.

퍼즐 한 세트는 N * N개의 조각으로 구성되어 있다.

퍼즐의 한 조각은 M * M 크기의 기본 정사각형 모양에서 각 변의 단위마다

1만큼 밖으로 돌출되어 있거나 평면이거나 안쪽으로 돌출되어 있다. (단, 꼭지점 부분은 항상 평면이다.)

다행히 각 변의 모양이 같은 것이 없어서 쉽게 짝을 찾아나갈 수 있었다.

퍼즐 조각을 맞추기를 거의 완성해 가는 중 잠깐 화장실을 간 사이에

막 걸음마를 시작한 동생이 어느새 퍼즐에 다가와서 그만 퍼즐을 엎어버리고 말았다.

어린 동생이 모르고 저지른 일이니 누구를 탓할 수도 없는 상황이라 침착하게 마음을 먹고 다시 조각을 맞추기 시작했다.

그런데 조각을 맞춰 나가다보니 조각들 중에 변의 모양이 같은 게 있는 것을 확인했다.

이상한 생각이 들어서 전체 조각의 개수를 세어보니 T개가 더 많은게 아닌가?

진상을 조사해 보니 동생이 다른곳에 있는 퍼즐 조각을 손에 들고 이리저리 돌아다니다가 정올이가 맞추던 퍼즐을 엎을 때 손에 들고 있던 조각들이 섞여 버린 것이다.

다행히 퍼즐 조각에 있는 그림의 모양을 보면 상하좌우는 구분이 가능하므로 퍼즐 조각을 돌려서 맞출 필요는 없다.

울상이 된 정올이를 위해 퍼즐을 맞추고 원래의 퍼즐 세트가 아닌 섞여진 조각을 찾아내는 프로그램을 작성해 주도록 하자.

입력

입력의 첫 번째 줄에는 N, M, T가 입력된다. (2 <= N <= 50, 6 <= M <= 16, 1 <= T <= 5)

다음 줄부터 (N * N + T) * 4줄에 걸쳐 각 퍼즐 조각의 정보가 입력된다.

한 개의 퍼즐 조각 정보는 오른쪽부터 시계방향으로 각 변의 상태를 나타내는 길이 M인 4개의 문자열로 이루어진다.

각 변의 상태는 왼쪽에서 오른쪽 또는 위에서 아래의 순서로 'M’, ‘0’, ‘F’세 개의 문자로 나타낸 문자열이며 각각 바깥돌출, 평면, 안쪽돌출을 나타낸다.

각 퍼즐조각은 입력되는 순서대로 0번부터 N * N + T - 1번까지 번호를 부여한다.

입력의 마지막 줄에는 출력하려는 퍼즐조각의 행과 열이 입력된다.

출력

출력의 첫 번째 줄에는 퍼즐을 맞추고 난 후 입력된 행과 열의 위치에 있는 퍼즐조각의 번호를 출력한다.

다음 줄에는 원래의 퍼즐 세트가 아닌 퍼즐 조각을 작은 번호부터 차례대로 공백으로 분리하여 T개를 출력한다.

퍼즐 조각 맞추기2 1s 256MB