Дана матрица из \(n\) строк и \(m\) столбцов, каждая ячейка которой имеет один из трех типов:
- Пустая ячейка (обозначается как «.»).
- Камень (обозначается как «*»).
- Препятствие (обозначается как строчная буква латинского алфавита «o»).
Каждый камень начинает падать, пока не окажется на полу (в нижней строке матрицы), в ячейке над препятствием, или в ячейке над другим камнем, который уже закончил падение. (Другими словами, все камни начинают падать и падают, пока под ними пустые ячейки.)
Просимулируйте процесс и выведите состояние матрицы после того, как все камни закончат падать.
Выходные данные
Для каждого набора входных данных выведите матрицу из \(n\) строк и \(m\) столбцов, описывающую результат процесса.
Не обязательно выводить новую строку после каждого набора входных данных; в примерах из условия она выводится для наглядности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 10
.*.*....*.
.*.......*
...o....o.
.*.*....*.
..........
.o......o*
2 9
...***ooo
.*o.*o.*o
5 5
*****
*....
*****
....*
*****
|
..........
...*....*.
.*.o....o.
.*........
.*......**
.o.*....o*
....**ooo
.*o**o.*o
.....
*...*
*****
*****
*****
|