Magic
Ron mixed several potion ingredients in a test tube and started observing the precipitate that formed.
Write a program to determine the shape of the precipitate. This involves simulating the process in a two-dimensional grid. All ingredients fall downward at the same speed. A group of ingredients will move down if there are no obstacles below (i.e., only empty cells are beneath them). If identical ingredients are in adjacent cells that share a side, they bond chemically and can only move downward together.
Input
The first line of the input contains two integers separated by a space, representing the dimensions of the test tube: N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 100). This is followed by N lines, each containing M characters, representing the initial state. The symbol "." (dot) indicates an empty cell (solution). Different potion ingredients are represented by different Latin letters (uppercase or lowercase, with case sensitivity) and numbers.
Output
Output N lines, each containing M characters, showing the resulting precipitate.