AlgoLiga 2018

Jan skończył studia z wyróżnieniem, a starty w licznych konkursach programistycznych pozwoliły mu znaleźć wymarzoną pracę... jest programistą w korporacji ;-) Właśnie poszedł na pierwszy w swojej karierze urlop i już pierwszego dnia uświadomił sobie, że przez roztargnienie zapomniał się wylogować na służbowym laptopie. Chciałby wrócić do firmy niepostrzeżenie i naprawić swój błąd jednak bardzo obawia się spotkania z szefem, który zapewne będzie zadawać wiele niewygodnych pytań. Nasz bohater ma swoje przypuszczenia odnośnie tego na których piętrach jego szef może przebywać o danej porze. Jan zdążył również zapamiętać sposób funkcjonowania wind w budynku i zna wszystkie połączenia pomiędzy piętrami. Nasz bohater postanowił, że napisze program który obliczy najkrótszy czas w jakim może znaleźć się na swoim piętrze, nie spotkawszy po drodze szefa. Napisz program za Jana stosując się do następujących zasad:

1. Budynek posiada n pięter i jest otwarty przez 480 minut numerowanych od 0.
2. Jan zjawi się w budynku na piętrze 0 o czasie 0.
3. Nasz bohater musi się dostać na piętro k.
4. Przejechanie jednego piętra trwa równo minutę.
5. Nie można wjechać na piętro jeżeli aktualnie znajduje się na nim szef, można to zrobić najwcześniej sekundę po tym jak je opuści.
6. Dozwolone jest czekanie na piętrze.
7. Przesiadanie się pomiędzy windami na danym piętrze jest pomijalnie krótkie.

Wejście

W pierwszej linii wejścia znajdują się cztery liczby całkowite n, k, p oraz s (1 ≤ n ≤ 100, 0 ≤ k < n, 1 ≤ p ≤ 600, 1 ≤ s < 400) oznaczające odpowiednio liczbę pięter w budynku, piętro na które Jan musi się dostać, liczbę połączeń między piętrami oraz liczbę przypuszczeń dotyczących tego gdzie może przebywać szef. W kolejnych p liniach znajdują się opisy połączeń pomiędzy piętrami. Każdy opis składa się z dwóch liczb a i b (0 ≤ a, b < n) określających pomiędzy, którymi piętrami kursuje dana winda. Uwaga! Winda zatrzymuje się tylko na piętrach a i b. W następnych s liniach znajdują się przypuszczenia odnośnie lokalizacji szefa. Każdy opis składa się z 3 liczb nr, t₁, t₂ oznaczających, że od minuty t₁ do minuty t₂ włącznie szef może się znajdować na piętrze numer nr.

Wyjście

Wypisz NIE jeżeli nie jest możliwe dotarcie na k-te piętro bez spotkania szefa albo TAK <minimalny_czas> w przeciwnym wypadku.

Przykład

Wejście

5 2 3 2
0 2
0 3
2 3
2 2 4
1 3 400

Wyjście

TAK 5