eolymp
bolt
Try our new interface for solving problems
Problems

Зельеделие

Зельеделие

Time limit 1 second
Memory limit 64 MiB

Рон смешал несколько ингредиентов зелья в пробирке и стал наблюдать за выпадающим осадком.

Напишите программу, которая рассчитает форму осадка. Расчёт выполняется для двумерного варианта задачи на поле из клеток. Все ингредиенты падают вниз синхронно с одинаковой скоростью. Группа ингредиентов движется вниз в случае, если движению ничего не мешает (т.е. под ней только пустые клетки). Если в соседних клетках, имеющих общую сторону, будут находиться одинаковые ингредиенты, то они становятся химически связанными и могут двигаться далее вниз только вместе.

Input data

В первой строке входного файла содержатся два целых числа, разделенных пробелом – размеры пробирки N (1N100) и M (1M100). Далее следует N строк, содержащих по M символов – начальное состояние. Символ "." (точка) означает пустую клетку (раствор). Различные ингредиенты зелья обозначены различными латинскими буквами (прописными или строчными, регистр букв важен) и цифрами.

Output data

В выходной файл вывести N строк, содержащих по M символов – получившийся осадок.

Examples

Input example #1
4 5
aBBB.
.aBcc
.BB..
.....
Output example #1
.....
.BBB.
aaB..
.BBcc