Problem description

– Kowalski! – piszczał Szeregowy.

– Kowalski! Co wyście zrobili?! – krzyczał Skipper. – Nawet nie zapytam was o opcje, bo nie chcę ich znać.

Zastanawiacie się, co takiego zrobił Kowalski? Odpowiedź jest prosta, stworzył prawdziwe monstrum żywiące się bitą śmietaną. Stworzył Żelusia. Problemu by nie było, gdyby nie to, że Żeluś przy każdym solidnym dostarczeniu energii się podwaja. No właśnie podwaja, jako programista powinieneś doskonale rozumieć, co to oznacza. Apokalipsa ma wykładniczy postęp, a świat skończy się za logarytmicznie wiele czasu.

Pingwiny już pogodziły się z tym, że nie uda im się wyjść cało z tej przygody. Co z tego, że w przyspieszonym procesie za winnego uznany został Kowalski, skoro kreatura pochłonie już za moment całe Zoo, a chwilę potem i cały świat. Można się tylko schować w miejscu Zoo, które zostanie najpóźniej przejęte, może akurat Kowalski wymyśli w tym czasie jakieś sensowne opcje (byle nie kontrpotwora, który zje Żelusia).

Zoo ma kształt prostokątnego placu o wymiarach N × M metrów i może w oczywisty sposób zostać podzielone na N ⋅ M kawałków jednostkowych. Kawałek jednostkowy może być jednoznacznie wyznaczony przez podanie jego współrzędnych X i Y, zgodnie z układem kartezjańskim. Jeśli w kawałku jednostkowym o współrzędnych X i Y znajduje się aktualnie przedstawiciel gatunku Żeluś, to w następnej jednostce czasu, w jednym z sąsiednich pól również będzie znajdował się przedstawiciel gatunku Żeluś (jeśli już się tam znajduje, to nic się nie dzieje, wynika to z miękkości Żelusia). Kowalskiemu udało się nawet zauważyć, że to, w jaką stronę przedstawiciele Żelusia “rozdwoją” w danej jednostce czasu zależy od jego kodu DNA, który Kowalskiemu jest dobrze znany. Jako że Żeluś jest tworem sztucznym, to jego DNA składa się z literek “G”, “D”, “L” i “P”.

Kowalski wyznaczył już nawet jaka literka DNA będzie odpowiadała za zachowanie się Żelusia w następnych Q jednostkach czasu. Ustalił również, jak poszczególne literki genotypu przekładają się na kierunek rozdwajania się Żelusia:

• “G” – Żeluś rozdwaja się w górę, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X i Y + 1,
• “D” – Żeluś rozdwaja się w dół, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X i Y − 1,
• “L” – Żeluś rozdwaja się w lewo, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X − 1 i Y,
• “P” – Żeluś rozdwaja się w prawo, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X + 1 i Y.

Twoim zadaniem będzie pomóc Pingwinom i napisać program, który na podstawie aktualnych pozycji Żelusia, wypisze czas, po jakim Żeluś przejmie całe Zoo oraz mapę Zoo z zaznaczonymi kawałkami jednostkowymi, które zajęte będą najpóźniej.

Uwaga: dla uproszczenia zakładamy, że świat poza Zoo nie istnieje, a przedstawiciele gatunku Żeluś wychodzący poza Zoo znikają. Możesz założyć, że Q jednostek czasu wystarczy Żelusiowi na pochłonięcie całego Zoo.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M i Q, pooddzielane pojedynczymi odstępami i oznaczające odpowiednio wymiary planszy oraz liczbę jednostek czasu, dla których Kowalski wyznaczył kierunek rozdwajania się Żelusiów.

W drugim wierszu znajduje się ciąg Q znaków, złożony z liter “G”, “D”, “L” i “P” i oznaczających kierunki rozdwajania się Żelusia w kolejnych jednostkach czasu.

W każdym z kolejnych N wierszy znajduje sią ciąg M znaków określających, w których kawałkach jednostkowych aktualnie znajduje się Żeluś, “#” odpowiada kawałkowi jednostkowemu, w którym znajduje się aktualnie przedstawiciel gatunku Żeluś, a “.” pusty kawałek jednostkowy.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba jednostek czasu, w których będzie istniał przynajmniej jeden kawałek jednostkowy niezajęty przez Żelusia. W każdym z kolejnych N wierszy należy wypisać ciąg M znaków “.” i “#”, reprezentujących Zoo, z zaznaczonymi kawałkami jednostkowymi, które zostaną zajęte jako ostatnie; kawałki jednostkowe, które zostaną zajęte jako ostatnie, powinny być oznaczone znakiem “.”, a pozostałe znakiem “#”.

Ograniczenia

1 ≤ N, M ≤ 1000, 1 ≤ Q ≤ 10 000.

Przykład

5 4 16
GLDPGLDPGLDPLLPP
....
.#..
....
.#..
....

8
###.
###.
###.
###.
###.

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.