Sirtet
시간 제한2초메모리 제한512 MB
서로 연결된 블록 덩어리를 하나의 강체로 보고 모두 같은 속도로 아래로 떨어뜨렸을 때, 맨 아래 바닥이나 다른 덩어리 위에 멈춘 뒤의 최종 격자를 출력한다.
문제
In a fancy new zero-person video game, Sirtet, the game is a rectangular grid with N rows and M columns. Before the game begins, some grid cells are blank (denoted as .) and others are filled (denoted as #). The filled squares represent a set of objects, and the filled squares that are adjacent (horizontally or vertically) should be considered to be part of the same rigid object. For example, this initial grid:
..#.
##.#
.##.
#...
#...
has four objects, shown below:
## # # #
## #
When the game begins, the objects fall straight down the grid, all at the same speed. Each object continues to fall straight down until it either touches the bottom row, or has some part of it land directly on top of another object, at which point it stops. What will be the final state of the grid?
입력
The first line contains two space-separated positive integers N and M (N · M ≤ 106).
The following N lines contain M characters each, describing the initial state of the grid. If the j-th column of the i-th row of the grid contains a block, the corresponding character in the input will be a #, otherwise it will be a . character.
출력
Output N lines contain M characters each, describing the final state of the grid. If the j-th column of the i-th row of the grid contains a block, the corresponding character in the input will be a #, otherwise it will be a . character.