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
#include <cstdio>
#include <cstdlib>

typedef struct {
	int id;
	int x1;
	int x2;
	int w;
} car;

car start[50000];
car end[50000];
int index[50000];

int comp(const void *x, const void *y)
{
	car a = *(car *)x;
	car b = *(car *)y;

	return a.x1 - b.x1;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, w;
		scanf("%d %d", &n, &w);
		for (int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			start[i].id = i;
			if (x1 > x2) {
				int tmp = x1;
				x1 = x2;
				x2 = tmp;
			}
			start[i].x1 = x1;
			start[i].x2 = x2;
			if (y1 > y2) {
				int tmp = y1;
				y1 = y2;
				y2 = tmp;
			}
			start[i].w = y2 - y1;
		}
		for (int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			end[i].id = i;
			if (x1 > x2) {
				int tmp = x1;
				x1 = x2;
				x2 = tmp;
			}
			end[i].x1 = x1;
			end[i].x2 = x2;
			if (y1 > y2) {
				int tmp = y1;
				y1 = y2;
				y2 = tmp;
			}
			end[i].w = y2 - y1;
		}
		qsort(start, n, sizeof(car), comp);
		qsort(end, n, sizeof(car), comp);
		for (int i = 0; i < n; i++) {
			index[end[i].id] = i;
		}
		for (int i = 0; i < n; i++) {
			start[i].id = index[start[i].id];
		}
		bool b = true;
		int n2 = n;
		for (int i = 0; i < n && b; i++) {
			for (int j = 1; j < n2 && b; j++) {
				if (start[j-1].id > start[j].id) {
					if (start[j-1].w + start[j].w <= w) {
						car tmp = start[j-1];
						start[j-1] = start[j];
						start[j] = tmp;
						n2 = j;
					} else {
						b = false;
					}
				}
			}
		}
		if (b) {
			printf("TAK\n");
		} else {
			printf("NIE\n");
		}
	}
}