Skoczek 1

Skoczek skacze po szachownicy o n rzędach i m kolumnach. Skoczka charakteryzują dwie liczby nieujemne (a, b), oznaczają one, że skoczek może wykonać skoki z pola o współrzędnych (x, y) na pola o współrzędnych (x+a, y+b), (x-a, y+b), (x+a, y-b), (x-a, y-b), (x+b, y+a), (x-b, y+a), (x+b, y-a), (x-b, y-a). Skoczek nie może wyskoczyć poza planszę. Dodatkowo, na szachownicy są poustawiane miny, na które jeśli skoczek wskoczy, to zginie. Dla danego pola początkowego i końcowego oblicz, w ilu minimalnie skokach skoczek jest w stanie przejść z pola startowego na pole końcowe, bez ginięcia po drodze.

Wejście

W pierwszym wierszu wejścia są 4 liczby n, m, a, b: 1 <= n, m <= 1000, 0 <= a, b <= 1000. Kolejne n wierszy zawiera po m znaków (oraz znak końca linii), oznaczające kolejne pola planszy; pole (i, j) reprezentuje j-ty znak w wierszu i+1. X oznacza minę, . wolne pole, S pole startowe, K pole końcowe. Będzie dokładnie jedno pole startowe i dokładnie jedno pole końcowe.

Wyjście

Wypisz minimalną liczbę skoków aby się dostać na pole końcowe, lub słowo NIE jeśli jest to niemożliwe.

Przykład

Dla wejścia:

7 8 2 3
.X....X.
..X..X..
X..X.X..
.X.X...X
..XX....
S.XX..K.
...X....

prawidłowym rozwiązaniem jest:

6