你是否曾经想过停车场管理员的工作是什么样的？表面上看，这似乎不是一份困难的工作：顾客留下车，你需要把它们停好。听起来很简单？事实可能并非如此，现实要复杂得多。停车场管理员面临的主要问题是他的老板。

有一天，老板命令他可怜的员工按照自己的意愿重新停放停车场里的所有车辆。管理员看着老板给他的纸条，又看着当前车辆停放位置的纸条，心想这是否真的可行。帮帮他吧！

我们将停车场表示为一个高度为 $w$ 的矩形（在平面上）。为了方便描述，我们建立一个坐标系，其坐标轴与矩形的边平行。坐标原点位于矩形的左下角。停车场足够宽，我们可以方便地假设矩形的右侧在无穷远处。

为了简化起见，我们将汽车也视为边与坐标轴平行的矩形。然而，汽车的大小各不相同，因此对应的矩形尺寸也可能不同。如果所有汽车都在停车场内，且没有任何两辆车占据停车场的同一部分，则停车场的停放状态是正确的。但我们允许代表汽车的矩形边界重叠。

停车场管理员已经有丰富的工作经验，因此他可以向任何方向移动汽车（形式上：管理员总是可以将任何汽车平移任意向量），只要汽车之间不发生碰撞即可。但他不能旋转汽车。

你的任务是确定是否可以将汽车从当前位置移动到老板指定的位置，且过程中不损坏任何车辆。

输入格式

输入的第一行包含测试用例的数量 $t$ ($1 \le t \le 20$)，后续依次描述每个测试用例。每个测试用例的第一行包含两个整数 $n, w$ ($1 \le n \le 50\,000, 1 \le w \le 10^9$)，分别表示停车场内的车辆数量和停车场的矩形高度。

接下来的 $n$ 行描述了汽车的初始位置：第 $i$ 行包含四个整数 $x_1, y_1, x_2, y_2$ ($0 \le x_1, x_2 \le 10^9, 0 \le y_1, y_2 \le w$)，描述了以点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 为对角顶点的矩形，该矩形对应于停车场中的第 $i$ 辆车。所有矩形的面积均为正。

接下来的 $n$ 行以相同的格式描述了汽车的目标位置。两个描述中的汽车顺序相同（初始位置描述中的第 $i$ 辆车对应目标位置描述中的第 $i$ 辆车）。同一辆车在目标位置描述中可能由不同的顶点坐标表示。你可以假设两个描述都是正确的。

在价值 5 分的测试用例中，满足额外条件 $n \le 1000$。

输出格式

输出 $t$ 行：第 $i$ 行应包含一个单词 TAK 或 NIE，取决于在第 $i$ 个测试用例中是否可以按照老板的要求重新停放车辆。

样例

输入 1

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

输出 1

TAK
NIE

说明 1

样例说明：上图展示了样例中的第一个测试用例。左侧显示了汽车的初始位置，右侧显示了目标位置。为了将 3 号车放入正确的位置，需要将 2 号车向下或向右移动。在第二个测试用例中，我们需要交换 1 号车和 2 号车的位置，这是不可能的。