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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define f first
#define s second

const int INF = 1000000009;
const int size = 50009;
const int Pow = 150000;

int z, n, W, H[size], D[Pow], p, where[size];
pair<int, int> A[size], B[size];

int extractMax(int a, int b) {
	if(b < 0) return -INF;
	a += p-1; b += p-1;
	int result = max(D[a], D[b]);
	while((a-1)/2 != ((b-1)/2)) {
		if(a%2) result = max(result, D[a+1]);
		if(b%2 == 0) result = max(result, D[b-1]);
		a = (a-1)/2;
		b = (b-1)/2;
	}
	return result;
}

void update(int a, int x) {
	a += p-1;
	D[a] = x;
	a = (a-1)/2;
	while(a != 0) {
		D[a] = max(D[2*a+1], D[2*a+2]);
		a = (a-1)/2;
	}
}

int main () {
	scanf("%d", &z);
	while(z--) {
		scanf("%d %d", &n, &W);
		for(int i = 0; i<n; i++) {
			int a, b, c, d;
			scanf("%d %d %d %d", &a, &b, &c, &d);
			if(a > c) swap(a, c);
			if(b > d) swap(b, d);
			A[i] = make_pair(a, i);
			H[i] = d-b;
		}
		for(int i = 0; i<n; i++) {
			int a, b, c, d;
			scanf("%d %d %d %d", &a, &b, &c, &d);
			if(a > c) swap(a, c);
			if(b > d) swap(b, d);
			B[i] = make_pair(a, i);
		}
		sort(A, A+n);
		sort(B, B+n);
		p = 1;
		while(p<n) p*=2;
		for(int i = 0; i<2*p+1; i++) D[i] = -INF;
		for(int i = 0; i<n; i++) D[p-1+i] = H[A[i].s];
		for(int i = p-2; i>=0; i--) D[i] = max(D[2*i+1], D[2*i+2]);
		bool success = true;
		for(int i = 0; i<n; i++) where[A[i].s] = i;
		for(int i = 0; i<n; i++) {
			int nr = B[i].s;
			int a = where[nr], h = H[nr];
			int m = extractMax(0, a-1);
			//printf("%d %d\n", nr, m);
			if(m != -INF && m+h > W) {
				success = false;
				break;
			}
			update(a, -INF);
		}
		if(success) printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}