Sparing w Programowaniu Zespołowym Politechnika Poznańska, 13.03.2004

Opis

Jasiu, jak codziennie po wyjściu ze szkoły, poszedł z kolegami na przystanek tramwajowy. Chłopiec nie wiedział jednak, że dzisiaj jego koledzy umówili się, że zrobią mu kawał. Postanowili nie pozwolić Jasiowi skasować biletu.
Kiedy tramwaj nadjechał wszyscy chłopcy weszli do środka. Jasiu niczego nie podejrzewając zaczął szukać biletu w kieszeni. W międzyczasie jego koledzy zajęli dogodne pozycje, tak by chłopiec miał jak najmniej szans na odbicie biletu. Jasiu zorientował się co koledzy knują i że nie będzie w stanie odbić biletu w kasowniku, przy którym stoi któryś z nich - jednak jest już za późno. Jego jedyną nadzieją na odbicie biletu jest ściganie się z kolegami (oraz odpowiednie manewrowanie), tak by udało mu się dotrzeć do jakiegoś "wolnego" kasownika. Jego koledzy nie dadzą jednak łatwo za wygraną i będą chcieli go uprzedzać, blokując kasowniki do których się kieruje.

Należy założyć, że chłopcy po tramwaju poruszają się tylko w jednym wymiarze - po linii prostej. Ich pozycja (jak i pozycja kasowników) jest jednoznacznie określona przez jedną współrzędną - odległość od przodu tramwaju. Jasiu może odbić bilet tylko wtedy, gdy zrówna się pod względem pozycji z którymś kasownikiem i żadnego z jego kolegów nie ma na tej samej pozycji co on. Każdy chłopiec (także Jasiu) ma pewną, charakterystyczną dla siebie, maksymalną prędkość, z którą może się poruszać. Można przyjąć, że każdy z nich może zarówno rozwinąć swoją maksymalną prędkość, jak i wyhamować w zerowym czasie. Można też przyjąć, że chłopcy mogą biegać po tramwaju bez przeszkód (nie ma spowalniających tłumów, zrzędliwych staruszek, czy krzyczącego motorniczego).

Zadanie jest oparte na faktach. Opisana sytuacja rzeczywiście miała miejsce w tramwaju nr 5 na przystanku na osiedlu Czecha w Poznaniu.

Zadanie

Dana jest liczba kolegów Jasia oraz ich maksymalne prędkości, liczba kasowników w tramwaju oraz ich pozycje, a także maksymalna prędkość Jasia i jego pozycja początkowa (miejsce wejścia do tramwaju). Twój program powinien stwierdzić czy kolegom może udać się kawał, tj. czy mogą się tak ustawić na początku (znając już pozycję początkową Jasia) i tak się poruszać (widząc jak on się porusza) by niezależnie od strategii Jasia nie był on w stanie odbić biletu.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (1 ≤ D ≤ 30), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajdują się dwie liczby całkowite N i M (1 ≤ N ≤ 10.000, 1 ≤ M ≤ 10.000), oznaczające odpowiednio liczbę złośliwych kolegów Jasia oraz liczbę kasowników w tramwaju. Drugi wiersz zestawu zawiera również dwie liczby całkowite - VJ i DJ (1 ≤ VJ ≤ 2.000.000.000, 0 ≤ DJ ≤ 2.000.000.000), które mówią jaka jest maksymalna prędkość Jasia oraz jaka jest jego początkowa pozycja. Kolejny wiersz zawiera N liczb całkowitych - maksymalne prędkości kolegów Jasia (z zakresu od 1 do 2.000.000.000). Czwarty i ostatni wiersz zestawu zawiera M liczb całkowitych - pozycje kasowników (z zakresu od 0 do 2.000.000.000). Nie istnieją dwa kasowniki na tej samej pozycji. Pozycje podane są w metrach, a prędkości w metrach na sekundę.

Specyfikacja wyjścia

Dla każdego zestawu należy wypisać jedną linię zawierającą słowo "TAK" jeżeli kolegom może udać się kawał lub "NIE" jeżeli Jasiu będzie w stanie odbić bilet.

Przykład

2
2 3
5 2
1 4
1 4 2
3 4
8 1000
3 8 1
4 3 1 0

NIE
TAK