Mirror Tender

Interview

Time limit1sMemory limit256 MB

Summary

Decide for each test case whether one workshop's width and height ranges contain every other workshop's ranges.

Level: Easy2 of 10
Topics: Intervals
Solved: No attempts yet

Problem

Bajtazar's company makes wooden wardrobes with mirrored doors. The company does the woodwork itself and subcontracts the mirrors.

A tender run by the company has just closed. $n$ workshops took part, and each one stated the mirror sizes it can produce. Every mirror is a rectangle. A workshop's bid gives the smallest and the largest width it can produce, and the smallest and the largest height. Mirrors cannot be rotated when a wardrobe is built.

If one workshop's bid covers all the other bids, meaning no other bidder offers a mirror size that this workshop cannot produce, that workshop wins the tender. If several workshops submit a covering bid, the one with the lowest price per square centimetre of mirror wins. If no such workshop took part, the review gets complicated and the award is delayed by a lot. Bajtazar wants to avoid a pointless argument, so he asked you to write a program that decides whether some workshop's bid covers all the other bids.

Input

The first line contains one integer $t$ ( $1 \le t \le 10$ ), the number of test cases. Descriptions of the $t$ test cases follow.

The first line of each description contains one integer $n$ ( $2 \le n \le 100\,000$ ), the number of mirror workshops that bid in the tender. Each of the next $n$ lines contains four integers $w_1$ , $w_2$ , $h_1$ , $h_2$ ( $1 \le w_1 \le w_2 \le 10^9$ , $1 \le h_1 \le h_2 \le 10^9$ ). That workshop can produce a mirror of every integer width $w$ and every integer height $h$ with $w_1 \le w \le w_2$ and $h_1 \le h \le h_2$ .

Output

Print exactly $t$ lines, one per test case. Line $i$ contains TAK if the $i$ -th test case has a workshop whose bid covers all the other bids, and NIE otherwise.

Examples5

Example 1

Input

Expected output

TAK
NIE
TAK

Example 2
Input
```
1
2
1 1 1 1
1 1 1 1
```
Expected output
```
TAK
```
Example 3
Input
```
1
2
1 10 1 10
3 4 5 6
```
Expected output
```
TAK
```
Example 4
Input
```
1
2
1 5 1 5
2 6 1 5
```
Expected output
```
NIE
```
Example 5
Input
```
1
2
1 10 2 5
2 3 1 6
```
Expected output
```
NIE
```