10139번 - Lustra 다국어

Firma Bajtazara zajmuje się produkcją drewnianych szaf z lustrzanymi drzwiami. Firma koncentruje się na jakości wyrobów z drewna, a produkcję luster zleca podwykonawcom.

Właśnie zakończył się jeden z przetargów zorganizowanych przez firmę Bajtazara. Wzięło w nim udział n zakładów, z których każdy złożył pewną ofertę rozmiarów produkowanych luster. Wszystkie lustra mają prostokątny kształt. Oferta każdego z zakładów przedstawia minimalną i maksymalną szerokość oraz minimalną i maksymalną wysokość produkowanych luster. Przy produkcji szaf luster nie można obracać.

Bajtazar wie, że jeśli do przetargu stanął zakład, którego oferta majoryzuje oferty wszystkich pozostałych, tzn. żaden inny oferent nie ma w ofercie rozmiaru luster, którego nie produkowałby ów zakład, to taki zakład z pewnością wygra przetarg (jeśli w przetargu wystąpi wiele zakładów o majoryzującej ofercie, wygra ten, który zaproponuje najniższą cenę centymetra kwadratowego lustra). W przeciwnym razie ocena ofert będzie skomplikowana, a rozstrzygnięcie przetargu znacząco się opóźni. Licząc na uniknięcie jałowych dyskusji, Bajtazar poprosił Cię o napisanie programu, który stwierdzi, czy oferta któregoś z zakładów majoryzuje oferty pozostałych zakładów.

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą t (1 ≤ t ≤ 10), oznaczającą liczbę przypadków testowych do rozważenia. Dalej następują opisy kolejnych przypadków testowych.

Pierwszy wiersz opisu zawiera jedną liczbę całkowitą n (2 ≤ n ≤ 100 000), oznaczającą liczbę zakładów produkcji luster, które złożyły oferty w przetargu organizowanym przez firmę Bajtazara. Każdy z kolejnych n wierszy zawiera po cztery liczby całkowite w₁, w₂, h₁, h₂ (1 ≤ w₁ ≤ w₂ ≤ 10⁹, 1 ≤ h₁ ≤ h₂ ≤ 10⁹). Liczby te oznaczają, że dany zakład może wyprodukować lustra o dowolnej całkowitej szerokości w i wysokości h spełniających w₁ ≤ w ≤ w₂ oraz h₁ ≤ h ≤ h₂.

Twój program powinien wypisać na wyjście dokładnie t wierszy, zawierających odpowiedzi dla poszczególnych zestawów testowych. W i-tym z tych wierszy powinno znaleźć się jedno słowo TAK lub NIE, w zależności od tego, czy w przetargu wziął udział zakład, którego oferta majoryzuje oferty wszystkich pozostałych oferentów.