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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>

using namespace std;

typedef struct coord {
	int x1;
	int x2;
	int y1;
	int y2;
} coord_t;

typedef struct car {
	coord_t src;
	coord_t dst;
	int height;
} car_t;

bool comp_cars(const car_t* a, const car_t* b) {
	return a->height > b->height;
}

bool check(car_t** sorted_cars, int cars_count, int park_width) {
	bool answer = true;
	int bi = 0;
	int ei;
	int curr_height;

	while (bi < cars_count && sorted_cars[bi]->height > park_width / 2) {
		ei = bi + 1;
		curr_height = sorted_cars[bi]->height;

		while (ei < cars_count && sorted_cars[ei]->height + curr_height > park_width) {
			if (sorted_cars[bi]->src.x1 < sorted_cars[ei]->src.x1) {
				if (sorted_cars[bi]->dst.x1 > sorted_cars[ei]->dst.x1) {
					return false;
				}
			} else {
				if (sorted_cars[bi]->dst.x1 < sorted_cars[ei]->dst.x1) {
					return false;
				}
			}
			++ei;
		}

		++bi;
	}

	return answer;
}

void one_case() {
	int cars_count;
	int park_width;
	car_t* cars;
	car_t** sorted_cars;

	cin >> cars_count >> park_width;

	cars = new car_t[cars_count];
	sorted_cars = new car_t*[cars_count];
	for (int i = 0; i < cars_count; ++i) {
		cin >> cars[i].src.x1 >> cars[i].src.y1 >> cars[i].src.x2 >> cars[i].src.y2;
		cars[i].height = cars[i].src.y2 - cars[i].src.y1;
		sorted_cars[i] = &(cars[i]);
	}

	for (int i = 0; i < cars_count; ++i) {
		cin >> cars[i].dst.x1 >> cars[i].dst.y1 >> cars[i].dst.x2 >> cars[i].dst.y2;
		cars[i].height = cars[i].dst.y2 - cars[i].dst.y1;
	}

	sort(sorted_cars, sorted_cars + cars_count, comp_cars);

	cout << (check(sorted_cars, cars_count, park_width) ? "TAK" : "NIE") << endl;

	delete [] cars;
	delete [] sorted_cars;

}

int main() {
	int tc;

	ios_base::sync_with_stdio(0);

	cin >> tc;
	while (tc--) {
		one_case();
	}

	return 0;
}