P1728 [PA 2014] Parking

Your boss orders you to move the cars in the parking lot into the arrangement he wants. The parking lot is a long rectangular strip with width $w$. We take its lower-left corner as the origin, and build a Cartesian coordinate system with axes parallel to the sides of the rectangle. The parking lot is very long, so we can assume it extends infinitely far to the right. Each car is an axis-aligned rectangle, and cars may have different sizes. You may translate the cars arbitrarily (but you may not rotate them), as long as they do not go out of the parking lot and do not collide with each other. Touching is allowed (that is, at any moment, the overlap area of any two cars is $0$). You know the current positions of all cars and the positions desired by your boss. You need to determine whether your boss’s task can be completed. 

The first line contains an integer $t$, the number of testdata. For each test case, the first line contains two integers $n, w$, representing the number of cars and the width of the parking lot. The next $n$ lines describe the current positions. The $i$-th line contains four integers $x_1, y_1, x_2, y_2$, meaning that car $i$ currently occupies the rectangle determined by $x_1, y_1, x_2, y_2$. (Note: it is possible that $x_1 > x_2$ or $y_1 > y_2$.) The next $n$ lines have the same format and meaning, describing the target positions of the cars.

Output $t$ lines. The $i$-th line should be `TAK` (yes) or `NIE` (no), indicating whether, in the $i$-th test case, the cars can be moved as required.

Constraints: for $100\%$ of the data, $1 \le t \le 20$, $1 \le n \le 5 \times 10^4$, $1 \le w \le 10^9$, $0 \le x_1, x_2 \le 10^9$, $0 \le y_1, y_2 \le w$。 Translated by ChatGPT 5