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

enum
{
	MAX = 50010
};

int x[MAX], h[MAX];
int ids[MAX];
int translator[MAX];

bool comp(int a, int b)
{
	return x[a] < x[b];
}

int abs(int x) { return (x<0)?-x:x; }

int tree[1<<17];

void tree_insert(int x, int val, int l, int r, int id)
{
	if(tree[id] < val) tree[id] = val;
	if(r-l == 1) return;
	int mid = (l+r)/2;
	if(x < mid)
		tree_insert(x, val, l, mid, id*2+1);
	else
		tree_insert(x, val, mid, r, id*2+2);
}

int tree_read(int a, int b, int l, int r, int id)
{
	if(r-l==1) return tree[id];
	if(a <= l && b >= r) return tree[id];
	int v1 = 0, v2 = 0;
	int mid = (l+r)/2;
	if(a < mid && b > l) v1 = tree_read(a,b,l,mid,id*2+1);
	if(b >= mid && a < r) v2 = tree_read(a,b,mid,r,id*2+2);
	return (v1>v2)?v1:v2;
}

int main()
{
	int t; scanf("%d", &t);
	for(int ii = 0; ii < t; ii++)
	{
			memset(tree,0,sizeof(tree));
		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);
			x[i] = (x1 < x2) ? x1:x2;
			h[i] = abs(y1-y2);
			ids[i] = i;
		}

		std::sort(ids,ids+n,comp);
		for(int i = 0; i < n; i++)
			translator[ids[i]] = i;
		
		for(int i = 0; i < n; i++)
		{
			int x1, y1, x2, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			x[i] = (x1 < x2) ? x1:x2;
			ids[i] = i;
		}
		std::sort(ids,ids+n,comp);
		bool good = 1;
		for(int i = n-1; i >= 0; i--)
		{
			int m = tree_read(0,translator[ids[i]],0,n,0);
			if(m+h[ids[i]] > w) {good = 0; break;}
			tree_insert(translator[ids[i]],h[ids[i]],0,n,0);
		}
		printf("%s\n",good?"TAK":"NIE");
	}
	return 0;
}