Sirtet

Sirtet은 제로 플레이어 비디오 게임이다. 게임은 $N$행 $M$열의 직사각형 격자에서 진행된다. 게임을 시작하기 전에 일부 칸은 빈칸(.)이고 나머지 칸은 채워져 있다(#). 상하좌우로 인접한 채워진 칸은 같은 강체 물체에 속한다. 예를 들어 다음 초기 격자에는 물체가 네 개 있다:

..#.
##.#
.##.
#...
#...

네 물체는 아래와 같다.

##     #    #     #
 ##    #           

게임이 시작되면 모든 물체가 같은 속도로 격자에서 곧장 아래로 떨어진다. 각 물체는 바닥 행에 닿거나, 물체의 일부가 다른 물체 바로 위에 놓일 때까지 계속 떨어지고, 그 순간 멈춘다. 게임이 끝났을 때 격자의 최종 상태는 어떠한가?

첫 줄에는 양의 정수 $N$과 $M$이 공백으로 구분되어 주어진다 ($N \cdot M \le 10^6$).

이어지는 $N$줄에는 각각 $M$개의 문자로 격자의 초기 상태가 주어진다. $i$행 $j$열에 블록이 있으면 해당 문자는 #이고, 없으면 .이다.

$N$줄에 걸쳐 각각 $M$개의 문자로 격자의 최종 상태를 출력한다. $i$행 $j$열에 블록이 있으면 #을, 없으면 .을 출력한다.