도자기 가게의 황소 (브론즈)
시간 제한2초메모리 제한512 MB
회전 없이 평행 이동한 두 조각이 겹치지 않고 원래 격자를 정확히 복원하는 쌍을 찾습니다.
문제
농부 존은 집을 조금 더 꾸미기로 했다. 동네 도자기 가게에 들른 존은 벽난로 위 선반에 딱 맞을 유리 소 장식을 발견하고 사기로 마음먹는다.
소 장식의 모양은 크기의 문자 격자로 주어진다(). '#'은 장식의 일부인 칸이고, '.'은 장식이 아닌 칸이다. 인 예는 다음과 같다.
#..#....
####....
########
.##.####
...####.
...#..#.
...#..#.
........
존이 값을 치르기 직전에 황소 한 마리가 가게를 헤집고 지나가면서 이 장식은 물론 선반 위 유리 제품도 여럿 깨뜨린다. 존의 장식은 조각 두 개로 깨졌고, 바닥에 흩어진 조각 개 사이에 섞여 버렸다(). 조각 개는 각각 원래 장식과 같은 형식의 문자 격자로 주어진다.
조각 개 가운데 존이 다시 붙여야 할 두 조각을 찾아라. 조각은 떨어질 때 회전하지도 뒤집히지도 않았으므로, 존은 두 조각을 가로세로로 평행 이동한 뒤 겹치기만 하면 된다. 두 조각이 정말 존의 장식에서 나온 것이라면, 원래 장식의 '#' 하나하나가 두 조각 중 정확히 하나에만 들어가도록 평행 이동할 수 있다. 즉 겹쳐 놓은 두 조각은 '#'을 공유하지 않고, 합치면 원래 모양과 정확히 같아진다.
조각은 가로로도 세로로도 원하는 만큼 평행 이동할 수 있지만, '#'이 하나라도 격자 밖으로 나가도록 옮길 수는 없다. 한 조각의 '#'이 한 덩어리로 이어져 있지 않을 수도 있다. 조각이 떨어진 덩어리 여러 개로 이루어진 경우, 그 조각을 옮길 때는 모든 덩어리를 같은 양만큼 옮긴다.
입력
첫째 줄에 과 가 공백으로 구분되어 주어진다. 다음 개 줄에 원래 장식의 모양을 나타내는 문자 격자가 주어진다. 이어지는 개 줄에 존이 바닥에서 찾은 조각 개의 격자가 차례로 주어진다.
출력
존의 장식을 이루는 두 조각의 번호를 공백으로 구분해 한 줄에 출력한다. 번호는 이상 이하이고, 작은 번호를 먼저 쓴다. 답은 항상 존재하며 유일하다.