Description

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.

Input Format

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 Format

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

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

TAK
NIE
TAK

Hint

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