Replicate Replicate Rfplicbte

자동 세포 제조 회사의 사장이 똑같은 부품을 대량 생산하는 공정을 새로 개발해 특허를 냈다. 이 공정은 각 칸이 비어 있거나 채워져 있는 2차원 격자를 쓴다. 세부 사항은 물론 영업 비밀이다.

먼저 복제하려는 부품 모양을 격자의 몇몇 칸에 채워 넣는다. 그다음 모든 칸이 동시에 상태를 바꾸는 갱신 단계를 반복한다. 한 칸의 다음 상태는 자기 자신과 이웃한 여덟 칸을 합한 아홉 칸으로 정해진다. 그중 채워진 칸이 홀수 개면 그 칸은 다음 단계에서 채워지고, 짝수 개면 비워진다. 그림 1은 채워진 칸 세 개짜리 간단한 모양이 복제되는 몇 단계를 보여 준다.

그림 1. 복제 과정.

그런데 공정에 결함이 생겼다. 갱신 단계가 하나 끝날 때마다 격자의 한 칸이 저절로 상태를 뒤집을 수 있다. 그림 2는 첫 번째 단계 뒤에 한 칸이, 세 번째 단계 뒤에 또 다른 한 칸이 뒤집혔을 때 일어날 수 있는 일을 보여 준다.

그림 2. 복제 과정에서 생긴 오류. 이 그림은 첫 번째 예제 입력에 해당한다.

원래 모양은 사라지고 복제가 끝난 결과만 남았다. 그 결과에는 오류가 섞여 있을 수 있다. 주어진 최종 모양을 만들어 낼 수 있는 가장 작은 시작 모양을 구하라. 시작 모양은 비어 있으면 안 된다. 갱신 단계는 0번 이상 진행되었고, 각 단계 뒤에 최대 한 칸이 저절로 뒤집혔다.

첫 줄에 최종 모양을 감싸는 최소 직사각형의 너비 $w$와 높이 $h$가 주어진다 ($1 \le w \le 300$, $1 \le h \le 300$).

다음 $h$개 줄에는 각각 문자 $w$개가 주어져 최종 모양을 나타낸다. 각 문자는 빈 칸을 뜻하는 '.' 또는 채워진 칸을 뜻하는 '#'이다. 첫 줄, 마지막 줄, 첫 열, 마지막 열에는 채워진 칸이 적어도 하나씩 있다.

주어진 최종 모양을 만들어 낼 수 있는, 크기가 가장 작으면서 비어 있지 않은 시작 모양을 출력한다. 모양의 크기는 그 모양을 감싸는 최소 직사각형의 넓이다. 빈 칸은 '.', 채워진 칸은 '#'으로 쓰고, 필요한 최소한의 행과 열만 써서 출력한다. 조건을 만족하는 가장 작은 시작 모양은 하나뿐이다.