CosmoSkoczek

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Zasady gry

Gra toczy się na planszy o wymiarach NxM (pola indeksujemy od 1, startując od lewego, górnego rogu). Na jednym z pól stoi CosmoSkoczek. Dwaj gracze na przemian wykonują ruchy, polegające na przesunięciu CosmoSkoczka o X pól w lewo i Y pól do góry. Listę dopuszczalnych ruchów gracze ustalają na początku rozgrywki. Przegrywa gracz, który nie może wykonać ruchu. Dodatkowo niektóre pola na planszy są dziurawe. Jeśli CosmoSkoczek stanie na dziurawym polu po raz K-ty w danej grze to gracz, który go tam ustawił, przegrywa. Aby nie było zbyt trudno na planszy znajdują się też HiperTeleporty. Jeśli gracz przesunie pionek na HiperTeleporta może (ale nie musi) wykonać dodatkowy ruch.

Zadanie

Napisz program, który dla każdej z danych początkowych pozycji CosmoSkoczka określi, czy gracz rozpoczynający może wygrać niezależnie od posunięć drugiego.

Wejście

W pierwszym wejściu mamy kolejno: N - liczbę wierszy i M - liczbę kolumn planszy, liczbę K oraz liczbę dostępnych ruchów - T. W następnych T wierszach zapisane są pary liczb naturalnych X i Y. Każda taka para oznacza, że w jednym ruchu CosmoSkoczka można przesunąć o X w lewo i o Y do góry. W kolejnych N wierszach zapisana jest plansza. Kropka symbolizuje normalne pole, litera H - HiperTeleporta, D - dziurę. Następnie mamy kilka początkowych pozycji CosmoSkoczka (kolejno nr wiersza i kolumny), dla których mamy stwierdzić czy gracz rozpoczynający grę ma strategię wygrywającą. Dane wejściowe kończą się liczbą 0.

Wyjście

Dla każdej pozycji początkowej CosmoSkoczka należy wypisać TAK lub NIE zależnie od tego, czy pierwszy gracz ma strategię wygrywającą.

Przykład

Dla danych wejściowych:

3 5 2 2
1 1
2 1
D....
.D.H.
.....
2 1
3 3
3 4
3 5
0

poprawnym wynikiem jest:

NIE
TAK
TAK
TAK

Możesz założyć, że początkowo CosmoSkoczek stoi na normalnym polu. Liczby N, M i T będą nie większe niż 100. Liczba K będzie nie większa niż 10^9.