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

const int MAXN = 50078;

struct rect {
	int id, height, x;
	rect (int _id = 0, int _height = 0, int _x = 0)
		: id(_id), height(_height), x(_x) {}
} a[MAXN], b[MAXN];

bool operator< (rect a, rect b) {
	return a.x < b.x || a.x == b.x && a.id < b.id;
}

int f[MAXN];
int n, N;
int t[4 * MAXN];

int get(int v, int L, int R, int l, int r) {
	if (l > r) return 0;
	if (L == R) return t[v];
	int mid = (L + R) / 2;
	return std::max(get(2 * v, L, mid, l, std::min(mid, r)),
					get(2 * v + 1, mid + 1, R, std::max(mid + 1, l), r));
}

void upd(int v, int L, int R, int x, int val) {
	if (L == R)
		t[v] = val;
	else {
		int mid = (L + R) / 2;
		if (x <= mid)
			upd(2 * v, L, mid, x, val);
		else
			upd(2 * v + 1, mid + 1, R, x, val);
		t[v] = std::max(t[2 * v], t[2 * v + 1]);
	}
}

int main() {
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	int qwe;
	scanf("%d", &qwe);
	while (qwe--) {
		int 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);
			a[i].height = abs(y2 - y1);
			a[i].id = i;
			a[i].x = std::min(x1, x2);
		}
		std::sort(a, a + n);
		// for (int i = 0; i < n; i++)
		// 	printf("%d %d %d\n", a[i].id, a[i].x, a[i].height);
		// init f
		for (int i = 0; i < n; i++)
			f[a[i].id] = i;
		// read b
		for (int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			b[i].height = abs(y2 - y1);
			b[i].id = i;
			b[i].x = std::min(x1, x2);
		}
		std::sort(b, b + n);
		// init segtree
		for (N = 1; N < n; N <<= 1);
		for (int i = 0; i < N; i++)
			t[N + i] = (i < n ? a[i].height : 0);
		for (int i = N - 1; i > 0; i--)
			t[i] = std::max(t[2 * i], t[2 * i + 1]);
		// queries
		bool ans = true;
		for (int i = 0; i < n; i++) {
			int id = b[i].id;
			int r = f[id];
			int h = get(1, 0, N - 1, 0, r - 1);
			// printf(">%d\n", h);
			if (h + b[i].height > w) {
				ans = false;
				break;
			}
			upd(1, 0, N - 1, r, 0);
		}
		if (ans)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	return 0;
}