В симуляторе клеточного автомата Конвея задано прямоугольное поле размером n x m. Каждая клетка либо жива, либо мертва. Живая клетка обозначается символом 'X', мёртвая — символом '.'.

Для каждой клетки рассматриваются все 8 соседних клеток: по горизонтали, вертикали и диагонали. Клетки, выходящие за границы поля, считаются мёртвыми.

Симулятор применяет к начальному полю ровно k шагов. На каждом шаге новое состояние всех клеток определяется одновременно по следующим правилам:

• живая клетка остаётся живой, если у неё ровно 2 или 3 живых соседа, иначе становится мёртвой;
• мёртвая клетка становится живой, если у неё ровно 3 живых соседа, иначе остаётся мёртвой.

Требуется вывести состояние поля после выполнения k шагов.

Входные данные

В первой строке даны три целых числа n, m и k.

В следующих n строках записано начальное состояние поля — по m символов в каждой строке. Каждый символ равен '.' или 'X'.

Выходные данные

Выведите n строк по m символов — состояние поля после k шагов симуляции.

Ограничения

• 1 <= n, m <= 200
• 0 <= k <= 200

Примеры

Пример 1

Входные данные

1 1 0
X

Выходные данные

X

Пример 2

Входные данные

3 3 1
...
.X.
...

Выходные данные

...
...
...