판타스마고리

에밀의 꿈에는 사람이나 동물이 다른 존재로 일그러지는 장면이 자주 나온다. 에밀은 꿈속의 신비로운 세계를 모두에게 보여 주고 싶어 하며, 물론 흑백으로 세상 최초의 애니메이션을 만들려고 한다. 잠에서 깨면 에밀은 꿈에 나온 처음 모습과 마지막 모습만 기억하고 변하는 과정은 기억하지 못한다. 그래서 첫 번째 그림을 두 번째 그림으로 바꾸는 단계를 자세히 적어, 이 "변형"을 재현해 달라고 부탁한다.

에밀의 그림은 세 가지 조건을 따른다. 첫째, 그림 가장자리의 모든 픽셀, 즉 가장 왼쪽 열, 가장 오른쪽 열, 맨 위 행, 맨 아래 행의 픽셀은 같은 색이다. 둘째, 그림에는 다음 형태의 $2 \times 2$ 정사각형이 없다. 또는

셋째 조건은 다음과 같다. 그림을 연결된 같은 색 영역으로 나눈다. 즉, 인접한 같은 색 픽셀이 항상 같은 영역에 속하도록 하는 가장 잘게 나눈 분할이다. 인접한 픽셀을 포함하는 두 영역은 서로 인접한다고 한다. 에밀의 그림에서는 모든 영역이 최대 두 개의 다른 영역과 인접하고, 가장자리 픽셀을 포함한 영역은 최대 한 개의 다른 영역과 인접한다.

크기가 $W \times H$로 같은 흑백 그림 두 장이 주어진다. 목표는 첫 번째 그림을 두 번째 그림으로 바꾸는 "변형"을 찾는 것이다. 그림 $A$에서 그림 $B$로 가는 변형은 $A$로 시작하고 $B$로 끝나는 그림들의 수열이며, 다음 조건을 만족한다.

• 첫 그림을 제외한 각 그림은 바로 앞 그림에서 비트 하나를 뒤집어 얻을 수 있다.
• 각 그림은 위의 세 가지 조건을 따른다.
• 변형 과정에서 각 색 영역의 개수는 변하지 않는다.

첫 줄에 공백으로 구분된 정수 $W$와 $H$가 주어진다. 이어서 첫 번째 그림을 위에서 아래로 $H$줄에 걸쳐 준다. 각 줄은 왼쪽에서 오른쪽으로 $W$개의 문자로 이루어지며, $k$번째 문자가 '.'이면 흰색, '#'이면 검은색 픽셀이다. 마지막으로 두 번째 그림을 같은 형식으로 $H$줄에 걸쳐 준다.

변형이 없으면 "IMPOSSIBLE"을 한 줄에 출력한다. 변형이 있으면 그중 하나를 출력한다. $k+1$번째 그림이 $k$번째 그림에서 열 $c$, 행 $r$의 픽셀을 뒤집어 얻어진다면, $k$번째 출력 줄에 쌍 $(c,r)$을 적는다. 여기서 $0 \le c < W$, $0 \le r < H$이며, $c=0$은 가장 왼쪽 열, $r=0$은 가장 위 행이다.

• $1 \le H \le 64$
• $1 \le W \le 103$
• 첫 그림과 마지막 그림은 서로 다르다.
• 출력에 포함된 픽셀 뒤집기는 최대 $250\,000$번이다.