떨어지는 사과

R행 C열 직사각형 격자가 있다. 각 칸은 비어 있거나, 사과가 놓여 있거나, 장애물이 놓여 있다. 빈 칸은 ., 사과는 a, 장애물은 #으로 나타낸다.

다음 규칙에 따라 중력을 적용한다.

• 장애물은 움직이지 않는다.
• 사과 바로 아래 칸이 비어 있으면 그 사과는 아래 칸으로 내려간다.

더 이상 내려갈 사과가 없을 때까지 규칙을 적용한 뒤, 격자의 마지막 상태를 출력한다. 규칙을 한 칸씩 반복해서 적용하는 방법은 큰 입력에서 시간이 부족하다.

첫 줄에 격자의 행 수 R과 열 수 C가 주어진다 ($1 \le R \le 50\,000$, $1 \le C \le 10$).

이어지는 R개의 줄에는 격자의 각 행이 위에서 아래 순서로 주어진다. 각 줄은 ., a, # 중 하나인 문자 C개로 이루어진다.

마지막 상태의 격자를 R개의 줄에 출력한다.