P5995 [PA 2014] Lustra

The Byteasar company specializes in outsourcing the production of wardrobes with mirrors. In a recent tender, $n$ factories participated in the bidding. All mirrors are rectangular. For each factory, the mirrors it can produce have their own minimum and maximum width, and minimum and maximum height. Mirrors cannot be rotated. If there exists a factory such that it can produce every mirror that all other factories can produce, then this factory will obviously win. If not, judging will be troublesome. Byteasar wants to know whether there exists a factory that satisfies the condition above.

The first line contains an integer $t$, the number of testdata. For each test case, the first line contains an integer $n$. The next $n$ lines each contain four integers $w1,w2,h1,h2$, meaning that the width $w$ and height $h$ of mirrors this factory can produce must satisfy $w_1\le w\le w_2,h_1\le h\le h_2$.

Output $t$ lines in total. Each line is `TAK` (yes) or `NIE` (no), indicating whether there exists a factory that satisfies the condition.

For $100\%$ of the data, $1\le t\le 10$, $2\le n\le 10^5$, $1\le w_1\le w_2\le 10^9$, $1\le h_1\le h_2\le 10^9$. Translated by ChatGPT 5