Problem description

Antek jest wężem i jak każdy wąż lubi pełzać po swojej planszy o wymiarach N × M. Jako że piękność Antka przewyższa tylko jego doświadczenie w pełzaniu po planszy, Antek pełza bardzo ostrożnie, tak by na pewno nigdy przypadkiem nie wpaść w swój dłuuugi ogon. Dokładnie:

• Antek zaczyna w polu o współrzędnych (1, 1) i początkowo przemieszcza się w prawo (rosnąco względem drugiej współrzędnej).

• Gdyby Wąż Antek miał przepełznąć do pola znajdującego się poza planszą, to zakręca on w prawo.

• Wąż Antek uważa, że pole, na które chciałby wejść, jest niebezpieczne, gdy znajduje się tam już jego ogon lub na co najmniej dwóch sąsiednich polach znajduje się jego ogon. Gdyby Wąż Antek miał przepełznąć do pola niebezpiecznego, to spróbuje zakręcić w prawo. Jeśli skręt w prawo również skutkowałby przepełznięciem na pole niebezpieczne, to Wąż Antek kończy pełzać.

Wąż Antek jest nieskończenie długi, dlatego jakaś jego część zawsze znajduje się poza planszą. Twoim zadaniem będzie narysowanie węża Antka w momencie, w którym przestanie on pełzać.

Napisz program, który wczyta wymiary planszy, wyznaczy jej stan, gdy Wąż Antek przestanie pełzać i wypisze go na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i oznaczające odpowiednio wysokość i szerokość planszy.

Wyjście

Na wyjście należy wypisać N wierszy, a w każdym z nich powinno znaleźć się M znaków # lub ., w zależności od tego, czy na danym polu planszy znajduje się Wąż Antek, czy nie.

Ograniczenia

0 ≤ N, M ≤ 200.

Przykład

2 2

##
.#

1 2

##

4 10

##########
.........#
#........#
##########

7 7

#######
......#
#####.#
#...#.#
#.###.#
#.....#
#######