Rak n Roll

Frodo i Samwise po długiej podróży dotarli w końcu na płaskowyż Gorgoroth, na którym znajduje się cel ich wyprawy - Góra Przeznaczenia. Przedstawmy płaskowyż jako planszę o m×n polach. Z każdego pola planszy możemy pójść w jednym z czterech kierunków: w górę, w dół, w lewo, w prawo. Na płaskowyżu znajdują się orkowie skupieni wokół ognisk. Ich dokładne pozycje nie są znane, wiadomo jednak, że żaden ork nie oddala się od ogniska dalej niż na odległość d pól. Zarówno hobbici jak i orkowie przemieszczają się pomiędzy polami według tej samej reguły podanej powyżej.

Frodo i Samwise chcą się dostać do Góry Przeznaczenia bezpieczną ścieżką, omijając wszystkie pola, na których potencjalnie mogą znajdować się orkowie. Odpowiedz na pytanie, jaka jest długość najkrótszej bezpiecznej ścieżki prowadzącej do Góry Przeznaczenia?

Wejście

W pierwszej linii wejścia znajdują się trzy liczby całkowite m ∈ [3, 1000], n ∈ [3, 1000] i d ∈ [1, 5] oznaczające odpowiednio liczbę wierszy i kolumn planszy oraz maksymalną odległość na jaką orkowie oddalają się od ogniska.

W kolejnych m liniach znajduje się opis planszy. Każda linia zawiera n znaków. Dopuszczalne znaki to:

• . - wolne pole
• O - pole, na którym znajduje się ognisko
• H - pole, na którym znajdują się Frodo i Samwise
• G - pole, na którym znajduje się Góra Przeznaczenia

Gwarantujemy, że na planszy występuje tylko jedno pole H i jedno pole G. Gwarantujemy również, że są one bezpieczne, czyli odległość do najbliższego ogniska jest większa od d. Takiej gwarancji nie dajemy w przypadku pól wolnych.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest długość najkrótszej bezpiecznej ścieżki prowadzącej do Góry Przeznaczenia. Jeżeli taka ścieżka nie istnieje należy wypisać -1.

Przykład 1

Wejście:

10 8 2
........
.O.O..O.
........
........
........
........
G.......
..O.....
........
...H...O

Wyjście:

14

Przykład 2

Wejście:

3 5 1
H....
.O.O.
....G

Wyjście:

-1