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

std::pair<int, std::pair<int, int> > start[51000], end[51000];
int mapping[51000];
const int size = (1 << 16);
int node[2*size];

void set(int p, int v) {
    for (p+=size, node[p]=v, p>>=1; p>0; p>>=1) node[p] = std::max(node[p<<1], node[(p<<1)+1]);
}

int find(int p, int k) {
    int m = 0;
    p+=size;
    k+=size;
    
    while (p<k) {
	if ((p & 1) == 1) m = std::max(m, node[p++]);
	if ((k & 1) == 0) m = std::max(m, node[k--]);
	p >>= 1;
	k >>= 1;
    }
    
    if (p==k) m = std::max(m, node[p]);
    return m;
}


int main() {
    int T;
    scanf("%d",&T);
    
    while (T--) {
	int N,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);
	    
	    int b = std::min(x1,x2);
	    int h = std::max(y1,y2) - std::min(y1,y2);
	    start[i] = std::make_pair(b, std::make_pair(h, i));
	}
	
	for (int i=0; i<N; ++i) {
	    int x1,y1,x2,y2;
	    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	    
	    int b = std::min(x1,x2);
	    int h = std::max(y1,y2) - std::min(y1,y2);
	    end[i] = std::make_pair(b, std::make_pair(h, i));
	}
    
	std::sort(start, start+N);
	std::sort(end, end+N);
	memset(node, 0, sizeof(node));
	
	for (int i=0; i<N; ++i) {
	    mapping[start[i].second.second] = i;
	    set(i, start[i].second.first);
	}
	
	bool ok = true;
	for (int i=0; i<N; ++i) {
	    int nr = end[i].second.second;
	    int height = end[i].second.first;
	    int pos = mapping[nr];
	    
	    if (height + find(0, pos-1) > W) {
		ok = false;
		break;
	    } else {
		set(pos, 0);
	    }
	}
	
	printf("%s\n",ok?"TAK":"NIE");
    }
    
    return 0;
}