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łby przepełzać 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ę już tam jego ogon lub na co najmniej dwóch sąsiednich polach znajduje się już ogon węża Antka. 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 jest 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

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