1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <vector>
#include <algorithm>

class Car {
public:
	int x1, x2, nx1, nx2, height;

	inline int getBegin() { return x1 < nx1 ? x1 : nx1; }
	inline int getEnd() { return x2 > nx2 ? x2 : nx2; }
	inline bool isForward() { return x1 < nx1; }
};

typedef std::vector<Car*> CarVector;

CarVector parking;

void swap(int& x, int& y) { int z = x; x = y; y = z; }

int main(int argc, char* argv[]) {
	int times;
	scanf("%d", &times);
	for(int t = 0; t < times; t++) {      // 1-20
		int cars, height, y1, y2;
		scanf("%d %d", &cars, &height);
		for(int c = 0; c < cars; c++) {
			Car* car = new Car;
			scanf("%d %d %d %d", &car->x1, &y1, &car->x2, &y2);
			car->height = (y2 - y1 < 0) ? y1 - y2 : y2 - y1;
			if(car->x1 > car->x2) swap(car->x1, car->x2);
			parking.push_back(car);
		}
		
		for(Car* car : parking) {
			scanf("%d %d %d %d", &car->nx1, &y1, &car->nx2, &y2);
			if(car->nx1 > car->nx2) swap(car->nx1, car->nx2);
		}

		std::sort(parking.begin(), parking.end(), [](Car* a, Car* b){ return a->getBegin() < b->getBegin(); });
		bool isNotPossible = false;
		for(CarVector::iterator it = parking.begin(); it != parking.end(); it++) {
			Car *a = *it;

			for(CarVector::iterator cit = it + 1; cit != parking.end(); cit++) {
				Car *b = *cit;

				if(a->getEnd() <= b->getBegin()) continue;

				if(a->height + b->height <= height) continue;

				if(a->isForward() == b->isForward()) {

					if(a->nx2 > b->nx1 || a->x2 > b->x2) {
						isNotPossible = true;
						break;
					}
				} else {
					isNotPossible = true;
					break;
				}
			}

			if(isNotPossible) break;
		}		
		
		if(isNotPossible) printf("NIE\n");
		else printf("TAK\n");
		parking.clear();
	}

	return 0;
}