#P1728. [PA2014] Parking

[PA2014] Parking

题目描述

你的老板命令你将停车场里的车移动成他想要的样子。

停车场是一个长条矩形,宽度为 ww。我们以其左下角顶点为原点,坐标轴平行于矩形的边,建立直角坐标系。停车场很长,我们可以认为它一直向右边伸展到无穷远处。

车都是边平行于坐标轴的矩形,大小可能不同。你可以将车任意地平移(但不能旋转),只要他们不超出停车场的边界,且不能互相碰撞,但紧挨着是允许的(即任意时刻任两辆车的重叠面积为 00)。

你知道目前各辆车的摆放位置,以及老板心中所想的位置。你需要判断是否可以办到老板的任务。

输入格式

第一行为一个整数 tt,表示测试数据数量。

对于每组测试数据,第一行两个整数 n,wn,w,分别表示车的数量和停车场的宽度。

接下来 nn 行,第 ii 行有四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示编号为 ii 的车的当前位置是由 x1,y1,x2,y2x_1,y_1,x_2,y_2 确定的矩形。

(注意:数据有可能出现 x1>x2x_1>x_2y1>y2y_1>y_2

再接下来 nn 行,格式和意义同上,表示车的目标位置。

输出格式

输出 tt 行,第 ii 行为 TAK(是)或 NIE(否),表示第 ii 组测试数据中能否按照要求进行移动。

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

提示

对于 100%100\% 的数据,1t201\le t\le 201n5×1041\le n\le 5\times 10^41w1091\le w\le 10^90x1,x21090\le x_1,x_2\le 10^90y1,y2w0\le y_1,y_2\le w