Bajtocka Wytwórnia Płytowa

Limit pamięci: 64 MB

Bajtazar koordynuje prace w Bajtockiej Wytwórni Płytowej. W wytwórni zatrudnionych jest kompozytorów oraz autorów tekstów. Twórcy pracują w dwuosobowych zespołach złożonych z jednego kompozytora oraz jednego autora tekstów.

Bajtazar wie, w czym specjalizują się pracownicy wytwórni, dzięki czemu potrafi ocenić, jak efektywnie będzie współpracować każdy z kompozytorów z każdym z autorów tekstów. Efektywność pracy każdej pary mierzy liczbą utworów napisanych w ciągu tygodnia.

Teraz chciałby on tak dobrać pracowników w rozłącznych par, aby każdego tygodnia produkowanych było łącznie jak najwięcej utworów. Twórcy, którzy nie będą mieli przydzielonego współpracownika, nie będą pracować.

Po przeanalizowaniu wszystkich danych Bajtazar stwierdził, że niezależnie od dokonanego podziału na pary, każdego tygodnia wszystkie zespoły będą łącznie produkowały tyle samo utworów. To spostrzeżenie wydało mu się zaskakujące, dlatego poprosił Cię o napisanie programu, który rozwieje jego wątpliwości.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę zestawów danych opisanych w następnych wierszach.

Każdy zestaw rozpoczyna się od wiersza z trzema liczbami całkowitymi , oraz (, ), które opisują kolejno liczbę kompozytorów i autorów tekstów w wytwórni oraz liczbę wierszy z opisem efektywności prac. Kompozytorzy są ponumerowani od do , zaś autorzy tekstów - od do .

W kolejnych wierszach znajdują się po cztery liczby całkowite , , oraz (, , ), które oznaczają, że w wyniku współpracy kompozytora z dowolnym z autorów tekstów o numerach od do powstanie utworów tygodniowo.

Każda para kompozytor - autor tekstów zostanie opisana w co najwyżej jednym wierszu. Mogą istnieć pary twórców niewymienione w żadnym wierszu; taka sytuacja oznacza, że owi dwaj twórcy specjalizują się w różnych, niekompatybilnych gatunkach muzyki i w związku z tym efektywność pracy takiej niewymienionej pary jest równa 0. Niemniej jednak taka para może tworzyć zespół.

Wyjście

Twój program powinien wypisać wierszy z odpowiedziami dla kolejnych zestawów testowych. Odpowiedzią dla jednego zestawu jest słowo TAK, jeśli dla każdego doboru pracowników w par, łączna efektywność pracy jest taka sama. W przeciwnym przypadku należy wypisać NIE.

Przykład

Dla danych wejściowych:

2
2 3 3
1 1 3 3
2 1 1 3
2 2 3 3
3 3 7
1 1 1 5
1 2 2 6
2 1 1 5
2 2 2 6
3 1 1 8
3 2 2 9
3 3 3 10

poprawną odpowiedzią jest:

TAK
NIE

Autor zadania: Krzysztof Diks.