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 <stdio.h>
#define N (1<<16)
int w[N*2];
#define MAX(x,y) x < y ? y : x
void insert(int x, int val) {
	int v = N + x;
	w[v] = MAX(w[v],val);
	while(v!=1) {
		v/=2;
		w[v] = MAX(w[2*v],w[2*v+1]);
	}
//	{ int i; for (i = 0; i < N * 2; i++) printf("%d ", w[i]); puts("");}
}
int query(int a, int b) {
	int va = N + a, vb = N + b;
	int wyn = w[va];
	if(va != vb) wyn = MAX(wyn,w[vb]);
	while(va/2 != vb/2) {
		if(va % 2 == 0) wyn = MAX(wyn,w[va+1]);
		if(vb % 2 == 1) wyn = MAX(wyn,w[vb-1]);
		va /= 2; vb /= 2;
	}
	return wyn;
}
void clr() {
		memset(w,0,sizeof(w));
}
int n;
int x1[N], x2[N], h[N];
int o1[N], o2[N], o3[N], s[N];
int cmp1(int *a, int *b) {
	return x1[*a] - x1[*b];
}
int cmp2(int *a, int *b) {
	return x2[*a] - x2[*b];
}
int main() {
	int c;
	scanf("%d",&c);
	while(c--) {
		int i,w,r=1;
		scanf("%d%d",&n,&w);
		//printf("%d %d %d\n", c, n, w);
		clr();
		for (i=0;i<n;i++) {
			int y,z,t;
			scanf("%d%d%d%d",x1+i,&y,&z,&t);
			h[i] = t - y;
			if (z < x1[i]) x1[i] = z; 
			if (h[i] < 0) h[i] = -h[i];
		}
		for (i=0;i<n;i++) {
			int y,z,t;
			scanf("%d%d%d%d",x2+i,&y,&z,&t);
			if (z < x2[i]) x2[i] = z; 
			o1[i] = o2[i] = i;
			s[i] = 0;
		}
		qsort(o1, n, sizeof(*o1), cmp1);
		qsort(o2, n, sizeof(*o2), cmp2);
		for (i=0;i<n;i++) {
			o3[o2[i]] = i;
		}
#if 0
		for (i=0;i<n;i++) {
			printf("%d ", o1[i]);
		}
		printf("-> ");
		for (i=0;i<n;i++) {
			printf("%d ", o2[i]);
		}
		printf("-> ");
		for (i=0;i<n;i++) {
			printf("%d ", o3[i]);
		}
		puts("");
#endif
		for (i=0;i<n;i++) {
			int b = o1[i], p = o3[b];
			int j;
			int mx = 0;
//			printf ("parking car %d of size %d at %d\n", b, h[b], p);
//			for (j = p+1; j< n;j++) {
//				printf ("... passing %d\n", s[n-1-j]);
//				mx = MAX(mx, s[n-1-j]);
//			}
//			printf ("A%d\n", mx);
			if (p<n-1) mx = query(0, n-1-p-1);
//			printf ("B%d\n", mx);
			if (w - mx < h[b]) break;
			s[n-1-p] = h[b];
			insert(n-1-p,h[b]);
		}
		puts(i==n?"TAK":"NIE");
	}
	return 0;
}