题目描述

题目译自 PA 2014 Runda 1 Lustra

Bajtazar 的公司专注于生产带镜门的木质衣柜。公司注重木制品的质量，而镜子的生产则外包给分包商。

最近，Bajtazar 公司组织的一场招标刚刚结束。有 $n$ 家工厂参与了招标，每家工厂都提交了关于其生产的镜子尺寸的报价。所有镜子均为矩形形状。每家工厂的报价包括其生产镜子的最小和最大宽度以及最小和最大高度。在生产衣柜时，镜子不能旋转。

Bajtazar 知道，如果招标中有一家工厂的报价主导了所有其他工厂的报价——即没有任何其他报价方能提供该工厂无法生产的镜子尺寸——那么这家工厂肯定会赢得招标（如果有多家工厂的报价均为主导报价，则报价每平方厘米镜子价格最低的工厂获胜）。否则，报价的评估将变得复杂，招标结果的确定会显著延迟。为了避免无谓的讨论，Bajtazar 请你编写一个程序，判断是否有某家工厂的报价主导了其他所有工厂的报价。

输入格式

输入数据的第一行包含一个整数 $t$ $(1 \leq t \leq 10)$，表示测试数据组数。接下来是各组测试数据的描述。

每组测试数据的第一行包含一个整数 $n$ $(2 \leq n \leq 100000)$，表示参与 Bajtazar 公司招标的镜子生产工厂数量。

接下来的 $n$ 行，每行包含四个整数 $w_{1}, w_{2}, h_{1}, h_{2}$ $(1 \leq w_{1} \leq w_{2} \leq 10^{9}, 1 \leq h_{1} \leq h_{2} \leq 10^{9})$。这些数字表示该工厂可以生产宽度 $w$ 和高度 $h$ 的任意整数尺寸镜子，满足 $w_{1} \leq w \leq w_{2}$ 以及 $h_{1} \leq h \leq h_{2}$。

输出格式

输出恰好 $t$ 行，包含各组数据的答案。第 $i$ 行应包含一个字符串 TAK 或 NIE，表示在招标中是否存在某家工厂的报价主导了所有其他工厂的报价。

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