Условие
Динозавр Дино чистит террариум магнитом: вытаскивает камни (символы 'x'), оставляя только песок ('0' → '-' после удаления). Магнит идёт по столбцам слева направо. В каждом столбце камни вынимаются сверху вниз. Когда камешек вытащен, песок и соседние камешки сдвигаются под действием гравитации.
Правила.
- Камешки выбираются столбец за столбцом слева направо. Магнит переходит к следующему столбцу, только когда в текущем не осталось ни одного
'x'. - Камни вынимаются сверху вниз внутри столбца.
- После вытаскивания камешка:
- Все песчинки в его столбце под ним падают вниз (только вниз).
- Песчинки из соседних столбцов (слева и справа) могут «переползти» в текущий столбец, если разница в высоте больше 1.
- Сначала падают песчинки справа, потом слева.
- Камешки не падают вниз сами по себе — они вытаскиваются.
- Камешки могут двигаться вверх через песок при освобождении ячеек — но это и есть «вынимание» (эквивалентно перемещению магнитом).
- Освободившиеся пустые ячейки маркируем символом
'-'.
Формат ввода
h # 1 ≤ h ≤ 10^6
w # 1 ≤ w ≤ 10^6, h * w ≤ 10^6
матрица h × w из символов '0' (песок) и 'x' (камень)
Формат вывода
Матрица h × w из '0' (оставшийся песок) и '-' (пустота).
Пример
Ввод:
4
5
0 0 0 0 x
0 x x 0 0
0 x 0 x 0
x 0 0 x 0
Вывод:
- - - - -
0 0 0 - -
0 0 0 0 0
0 0 0 0 0