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 <bits/stdc++.h>

#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define BCK(a,b,c) for(int a=(b); a>(c); --a)
#define st first
#define nd second

using namespace std;

const int MAXN = 50010;
const int MAXD = 128*1024+3;

struct car {
	int i, x1, x2, y1, y2;	
};

inline bool cmp(const car &a, const car &b){
//	if(a.x1 == b.x1)
//		return a.y1 < b.y1;
	return a.x1 < b.x1;
}

int n, w, d;
car S[MAXN];
car D[MAXN];
int height[MAXD];
int where[MAXN];

void hset(int x, int y){
	x += d;
	height[x] = y;
	x /= 2;
	while(x){
		height[x] = max(height[2*x], height[2*x+1]);
		x /= 2;
	}
}

int hget(int x, int y){
	x += d, y += d;
	int r = 0;
	while(x < y){
		if(x&1){
			r = max(r, height[x]);
			++x;
		}
		if((y&1)==0){
			r = max(r, height[y]);
			--y;
		}
		x /= 2;
		y /= 2;
	}
	if(x == y)
		r = max(r, height[x]);
	return r;
}

int main(){
	int z; scanf("%d", &z); while(z--){
		scanf("%d %d", &n, &w);
		d = 1;
		while(d < n) d *= 2;
		FWD(i,0,n){
			scanf("%d %d %d %d", &S[i].x1, &S[i].y1, &S[i].x2, &S[i].y2);
			if(S[i].x2 < S[i].x1) swap(S[i].x1, S[i].x2);
			if(S[i].y2 < S[i].y1) swap(S[i].y1, S[i].y2);
			S[i].i = i;
		}
		FWD(i,0,n){
			scanf("%d %d %d %d", &D[i].x1, &D[i].y1, &D[i].x2, &D[i].y2);
			if(D[i].x2 < D[i].x1) swap(D[i].x1, D[i].x2);
			if(D[i].y2 < D[i].y1) swap(D[i].y1, D[i].y2);
			D[i].i = i;
		}
		sort(S, S+n, cmp);
		sort(D, D+n, cmp);
		FWD(i,0,n) where[S[i].i] = i;
		FWD(i,0,n) height[d+i] = S[i].y2 - S[i].y1;
		BCK(i,d-1,0) height[i] = max(height[2*i], height[2*i+1]);
		bool err = false;
		FWD(i,0,n){
			int s = where[D[i].i];
			if(hget(0, s-1) + hget(s,s) > w){
				err = true;
				break;
			}
			hset(s, 0);
		}
		if(err) printf("NIE\n"); else printf("TAK\n");
	}
	return 0;
}