시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB0000.000%

문제

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 startiendiaibi, co oznacza, że dany pracownik podjął pracę w momencie starti, rzucił ją (albo praca rzuciła jego) w momencie endi, a jego efektywność w momencie t wyraża się wzorem ai*t + bi.

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 aibi to liczby całkowite z zakresu (-106, 106). W szczególności:

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

Liczby startiendi to liczby całkowite z zakresu (0, 106). 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 <= 105 ) oznaczająca liczbę pracowników w historii firmy. W kolejnych N liniach opisywani są pracownicy, każdy przez cztery oddzielone spacjami liczny naturalne startiendiaib( 0 <= startiend<= 106 ) ( -106 <= aibi <= 106 ).

출력

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.

예제 입력 1

3
2
0 5 0 3
0 5 0 2
2
0 5 0 3
0 5 0 3
2
0 2 1 0
0 2 -1 2

예제 출력 1

NIE
TAK
TAK

출처

Contest > Spot > CoolSpot 2011 3-4번