[AdditionalFile5296.zip](file://AdditionalFile5296.zip?type=additional_file)

#5296. 「PA 2014」Parking

标签: 传统 | 时间限制: 8500 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Runda 3 Parking

你有没有想过停车场管理员的工作是怎样的？表面上看，这似乎不是一份困难的工作：客户把车留下，需要将其停放好。很简单？看似如此，但现实要复杂得多。我们这位停车管理员的主要问题是他的老板。

有一天，老板命令可怜的员工按照他的心意重新排列停车场上的所有车辆。停车管理员看着老板递来的纸条和记录当前车辆摆放位置的纸条，疑惑这是否可能实现。请帮助他！

我们将停车场表示为一个高度为 $w$ 的矩形（在平面上）。为方便描述，我们采用与矩形边平行的直角坐标系，坐标原点位于矩形的左下角。停车场的宽度足够大，为了方便，我们假设矩形的右边无限远。

为了简化，车辆也被视为与坐标轴平行的矩形。不过，车辆有大有小，因此对应的矩形可能大小不同。停车场上车辆的摆放是有效的，如果所有车辆都在停车场内，且停车场的任何部分都不被两辆车同时占用。但允许表示车辆的矩形边界相互重叠。

停车管理员有丰富的经验，因此他可以任意方向移动车辆（形式上来说，停车管理员可以始终将任何车辆按任意向量移动），只要车辆不相互碰撞即可。但他不能旋转车辆。

你的任务是判断是否可以从当前位置将车辆重新排列到老板指定的位置，而不损坏任何车辆。

输入格式

输入数据的第一行包含测试数据组数 $t$ $(1 \leq t \leq 20)$，接下来的部分依次描述各组测试数据。

每组测试数据的描述从一行开始，包含两个整数 $n, w$ $(1 \leq n \leq 50000, 1 \leq w \leq 10^{9})$，分别表示停车场上的车辆数量和停车场矩形的高度。

接下来的 $n$ 行描述车辆的初始摆放位置：第 $i$ 行包含四个整数 $x_{1}, y_{1}, x_{2}, y_{2}$ $(0 \leq x_{1}, x_{2} \leq 10^{9}, 0 \leq y_{1}, y_{2} \leq w)$，描述一个对角顶点为 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$ 的矩形，对应停车场上的第 $i$ 辆车。所有矩形的面积均为正。

接下来的 $n$ 行描述车辆的目标摆放位置，格式相同。两个描述中的车辆按相同顺序给出（初始摆放描述中的第 $i$ 辆车对应目标摆放描述中的第 $i$ 辆车）。同一辆车在目标摆放中可能以不同于初始摆放的顶点描述。你可以假设两个描述都是合法的。

输出格式

输出应包含 $t$ 行：第 $i$ 行应包含 TAK 或 NIE，表示在第 $i$ 个测试用例中是否可以按照老板的要求重新排列车辆。

样例

输入

2
3 3
0 0 2 2
2 1 4 3
4 0 6 1
0 0 2 2
2 1 4 3
0 2 2 3
3 3
0 0 2 2
2 1 4 3
4 0 6 1
2 1 4 3
0 0 2 2
4 0 6 1

输出

TAK
NIE

图示展示了样例中的第一组测试数据。左侧显示了车辆的初始摆放位置，右侧显示了目标摆放位置。为了将车辆 $3$ 放置到合适位置，必须将车辆 $2$ 向下或向右移动。在第二组测试数据中，我们需要交换车辆 $1$ 和 $2$ 的位置，这是无法实现的。

数据范围与提示

对于 $50\%$ 的数据，$n \leq 1000$。