8803번 - Nigdy nie mów nigdy 다국어

문제

I jak ja mam ustalić płace dla moich pracowników? - pomyślał dyrektor Karierowitch - Chciałbym, aby każdy otrzymywał wynagrodzenie proporcjonalne do swojej efektywności. Ale efektywność pracowników ciągle się zmienia, a w dodatku pewnie nigdy nie będę miał w firmie dwóch pracowników o takiej samej efektywności.

Od dnia tych rozważań minęło wiele lat. W międzyczasie przez firmę dyrektora Karierowitcha przewinęło się w sumie N pracowników. Każdy z nich jest opisany przez liczby start_i, end_i, a_i, b_i, co oznacza, że dany pracownik podjął pracę w momencie start_i, rzucił ją (albo praca rzuciła jego) w momencie end_i, a jego efektywność w momencie t wyraża się wzorem a_i*t + b_i.

Twój program powinien sprawdzić czy istnieje moment w historii firmy, w którym pewna para aktualnych pracowników miała tę samą efektywność.

Liczby a_i, b_i to liczby całkowite z zakresu (-10⁶, 10⁶). W szczególności:

• a_i może być ujemna
• efektywność pracownika może być ujemna ( odpowiada to działaniu na szkodę firmy zamiast wypracowywania dla niej zysku )

Liczby start_i, end_i to liczby całkowite z zakresu (0, 10⁶). W poszukiwaniu momentu, w którym pewna para aktualnych pracowników ma tę samą efektywność, należy rozpatrywać wszystkie momenty rzeczywiste. Przedział czasu pracy w firmie jest obustronnie domknięty.

입력

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

W pierwszej linii opisu pojedynczego zestawu testowego znajduje się jedna liczba naturalna N ( 1 <= N <= 10⁵ ) oznaczająca liczbę pracowników w historii firmy. W kolejnych N liniach opisywani są pracownicy, każdy przez cztery oddzielone spacjami liczny naturalne start_i, end_i, a_i, b_i ( 0 <= start_i, end_i <= 10⁶ ) ( -10⁶ <= a_i, b_i <= 10⁶ ).

출력

Dla każdego zestawu testowego należy w osobnej linii wypisać "TAK", jeśli istnieje moment, w którym pewna para pracowników miała tę samą efektywność i "NIE" w przeciwnym wypadku.

제한

힌트