중력

$N \times M$ 크기의 이진 행렬이 주어진다. 셀 $(i, j)$에 문자 .이 있으면 빈 칸이고, 문자 #이 있으면 조각이 차지한 칸이다. 4방향으로 연결된 #의 각 극대 연결 요소가 하나의 조각을 이룬다. 조각은 나눌 수 없다. 아래 과정에서 조각이 합쳐지거나 쪼개지지 않는다. 같은 조각에 속한 모든 칸은 함께 움직인다.

모든 조각은 같은 속도로 바닥(마지막 행)을 향해 떨어지기 시작한다. 조각은 회전하지 않고 곧바로 아래로 움직인다. 1초마다 모든 조각이 한 행씩 내려가려고 한다. 이동한 결과 조각이 행렬의 아래쪽 경계를 넘으면 그 조각은 제자리에 멈춘다. 이동한 결과 다른 조각과 겹치면, 움직이려던 조각이 제자리에 멈춘다. 이런 겹침은 다른 조각이 움직이지 않을 때만 일어난다. 즉 조각은 바닥에 닿거나 다른 조각에 부딪히면 멈춘다.

모든 조각이 멈춘 뒤의 행렬 최종 상태를 출력하라.

첫 줄에 두 정수 $N$과 $M$이 주어진다 ($1 \le N, M \le 2000$). 이어지는 $N$개의 줄에는 각각 $M$개의 문자가 주어지며, 각 문자는 . 또는 #이다. 같은 줄의 문자는 공백 없이 붙어 있다.

모든 조각이 멈춘 뒤의 행렬을 입력과 같은 형식으로 출력한다. 다만 크기를 나타내는 첫 줄은 출력하지 않는다.