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

const int r = 1<<16;
const int maxN = 50 * 1000 + 10;
int tree[r<<1];
int n, maxH;
int h[maxN];
int posX[maxN];
int I[maxN];
int whereIs[maxN];
int whereTo[maxN];

int getMax(int a, int b);
void setVal(int x, int val);

int abs(int x) { return x < 0 ? -x : x; }
int min(int a, int b) { return a < b ? a : b; }

bool start() {
	scanf("%d%d", &n, &maxH);
	for(int i = 0; i < n; ++i) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		h[i] = abs(y1 - y2);
		posX[i] = min(x1, x2);
		I[i] = i;
	}
	std::sort(I, I + n, [](int a, int b) { return posX[a] < posX[b];});
	for(int i = 0; i < n; ++i) {
		whereIs[I[i]] = i;
		setVal(I[i], h[i]);
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		posX[i] = min(x1, x2);
	}
	std::sort(I, I + n, [](int a, int b) { return posX[a] < posX[b];});
	bool ok = true;
	for(int i = 0; i < n; ++i) {
		int what = I[i];
		if(h[what] + getMax(0, whereIs[what] - 1) > maxH)
			ok = false;
		setVal(whereIs[what], 0);
	}
	return ok;
}

int main() {
	int z;
	scanf("%d", &z);
	while(z--) {
		printf("%s\n", start() ? "TAK" : "NIE");
	}
	return 0;
}

int getMax(int a, int b) {
	a += r;
	b += r;
	int mx = 0;
	while(a < b) {
		if(a & 1) {
			mx = tree[a] > mx ? tree[a] : mx;
			a >>=1; ++a;
		}
		else a >>= 1;
		if(b & 1) b >>= 1;
		else {
			mx = tree[b] > mx ? tree[b] : mx;
			b >>= 1; --b;
		}
	}
	if(a == b)
		mx = mx < tree[a] ? tree[b] : mx;
	return mx;
}

void setVal(int x, int val) {
	x += r;
	tree[x] = val;
	x >>= 1;
	while(x) {
		tree[x] = tree[x << 1] > tree[(x << 1) + 1] ? tree[x << 1] : tree[(x << 1) + 1];
		x >>= 1;
	}
}