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

#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
#define ABS(X) ((X) >= 0 ? (X) : (-X))

#define MAX_N 50000
#define MAX_POW 131072

struct car {
	int x;
	int h;
	int data;
};

bool sort_x(struct car a, struct car b) {
	return a.x < b.x;
}

int next_pow(int x) {
	int i = 1;
	
	while (i < x)
		i <<= 1;
	return i;
}


int main() {
	
	int t, n, w;
	struct car before[MAX_N], after[MAX_N];
	int x1, x2, y1, y2;
	int tree[MAX_POW];
	int outer, now, prev, right;
	bool res;

	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		scanf("%d %d", &n, &w);

		for (int j = 0; j < n; j++) {
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			before[j].x = MIN(x1, x2);
			before[j].h = ABS(y2 - y1);
		}

		for (int j = 0; j < n; j++) {
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			after[j].x = MIN(x1, x2);
			after[j].h = ABS(y2 - y1);
			after[j].data = j;
		}

		std::sort(after, after + n, sort_x);
		for (int j = 0; j < n; j++) {
			int num = after[j].data;
			before[num].data = j;
		}
		std::sort(before, before + n, sort_x);

		outer = next_pow(n);
		for (int j = 0; j < 2 * outer; j++)
			tree[j] = 0;

		res = true;
		for (int j = 0; j < n && res; j++) {
			now = outer + before[j].data;
			tree[now] = before[j].h;

			while (now > 1) {
				prev = now;
				now = now / 2;
				tree[now] = MAX(tree[now], before[j].h);

				if (2 * now == prev) { // we were at left son
					right = 2 * now + 1;
					if (tree[right] + before[j].h > w)
						res = false;
				}
			}
		}
		
		if (res)
			printf("TAK\n");
		else
			printf("NIE\n");
	}

	return 0;
}