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
96
97
#include <cstdio>
#include <algorithm>
struct Car {
	int x, h, id;
	Car () {x = h = id = 0;}
	Car (int _x, int _h, int _id) {x = _x; h = _h; id = _id;}
};
int t, n, w, in_x1, in_x2, in_y1, in_y2, poz [50000], tree [140000], il, akt;
bool ok;
Car s [50000], k [50000];

int max (int a, int b) {
	return (a>b) ? (a) : (b);
}
int abs (int a) {
	if (a < 0) return -1*a;
	return a;
}
int min (int a, int b) {
	return (a<b)?(a) :(b);
}

bool cmp (Car a, Car b) {
	return a.x < b.x;
}

void update_all () {
	for (int i = il-1; i > 0; i --) {
		tree [i] = max(tree [2*i], tree [2*i+1]);
	}
}

void update (int a) {
	a += il;
	do {
		a /= 2;
		tree [a] = max(tree [a*2], tree [a*2+1]);
	} while (a != 1);
}
int get_max (int l, int p) {
	l += il;
	p += il;

	int ret = max(tree [l], tree [p]);

	while (l/2 != p/2) {
		if (l%2 == 0) ret = max(ret, tree [l+1]);
		if (p%2 == 1) ret = max(ret, tree [p-1]);

		l /= 2;
		p /= 2;
	}

	return ret;
}

int main () {
	scanf ("%d", &t);
	while (t--) {
		for (int i = 0; i <= 2*il; i ++) tree [i] = 0;
		scanf ("%d %d", &n, &w);

		for (il = 1; il < n; il *= 2);

		for (int i = 0; i < n; i ++) {
			scanf ("%d %d %d %d", &in_x1, &in_y1, &in_x2, &in_y2);
			s [i] = Car (min (in_x1, in_x2), abs(in_y2 - in_y1), i);
			}
		for (int i = 0; i < n; i ++) {
			scanf ("%d %d %d %d", &in_x1, &in_y1, &in_x2, &in_y2);
			k [i] = Car (min (in_x1, in_x2), abs (in_y2 - in_y1), i);
		}

		std::sort (s, s + n, cmp);
		std::sort (k, k + n, cmp);


		for (int i = 0; i < n; i ++) {
			poz [s [i].id] = i;	
			tree [il+i] = s [i].h;
		}

		update_all ();
		
		ok = true;
		for (int i = 0; i < n && ok; i ++) {
			akt = k [i].id;
			tree [il + poz [akt]] = 0;
			update (poz [akt]);
			
			if (w - get_max (0, poz [akt]) < k [i].h) ok = false;
		}

		if (ok) printf ("TAK\n");
		else printf ("NIE\n");
	}
}