8785번 - Dlaczego oni śpiewają? 다국어

Czy wiecie, że wśród rozlicznych mocnych stron Hektora znajduje się także doskonały słuch muzyczny? Czasem jednak staje się to dla niego prawdziwym utrapieniem, gdyż czyni słuchanie fałszujących ludzi szczególnie nieprzyjemnym doświadczeniem.

Dzisiaj w szkole Hektora odbywa się casting do programów Dlaczego oni śpiewają?, oraz Gwiazdy śpiewają pod lodem. Dziedziniec przed szkołą wypełnił się oczekującymi na swoją kolej uczestnikami, z których każdy rozgrzewa się fałszując niemiłosiernie.

Czy da się przejść przez dziedziniec tak, aby nie usłyszeć żadnego z fałszujących uczestników?

Dziedziniec ma kształt prostokąta o wysokości N i szerokości M. Wyróżniamy na nim (N+1)*(M+1) punktów o współrzędnych całkowitych, z punktem (0,0) w lewym górnym rogu i punktem (N,M) w prawym dolnym rogu. 

Na dziedzińcu stoi K fałszujących osób, każdą opisują współrzędne punktu P_i, w którym stoi, oraz zasięg fałszowania, to znaczy promień okręgu o środku w P_i w którym słychać daną osobę.

Fałszujące osoby stoją w punktach o współrzędnych całkowitych, ale Hektor (to w końcu jego szkoła i jego dziedziniec!) może poruszać się dowolną nie wychodzącą poza dziedzinieć ścieżką o rzeczywistych współrzędnych kolejnych punktów.

Sprawdź, czy istnieje ścieżka o współrzędnych rzeczywistych łącząca dowolny punkt na dolnej krawędzi dziedzińca (czyli punkt o współrzędnych (N,a) dla dowolnego rzeczywistego a z przedziału od 0 do M) z dowolnym punktem na górnej krawędzi (czyli punktem o współrzędnych (0,b) dla dowolnego rzeczywistego b z przedziału od 0 do M), która nie wychodzi poza obszar dziedzińca i nie przechodzi przez obszary fałszowania żadnej ze śpiewających osób. 

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii opisu zestawu znajdują się trzy oddzielone spacjami, opisane w treści liczby całkowite N, M i K ( 1 <= N, M <= 1000, 1 <= K <= 1000 ). Następnie w K kolejnych liniach opisywane są kolejne fałszujące osoby. Każdą opisują trzy oddzielone spacjami liczby całkowite w_i, c_i, r_i ( 0 <= w_i <= N, 0 <= c_i <= M, 1 <= r_i <= 1000 ), gdzie (w_i,c_i) oznaczają współrzędne danej osoby, a r_i jej zasięg fałszowania.  

Dla każdego zestawu testowego należy w osobnej linii wypisać "TAK", jeśli poszukiwana ścieżka istnieje i "NIE" w przeciwnym wypadku.