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 <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int n,w,M;
const int R = 65536;
int tab[2 * R + 1];
struct prostokat
{
	int x;
	int h;
	int pozycja;
};
int wskaznik[50010];
prostokat t[50010]; 
prostokat wzor[50010];
void insert(int x, int w)
{
	 x += M;
	 tab[x] = w;
	 x /= 2;
	 while(x > 0)
	 {
		 tab[x] = max(tab[2 * x], tab[2 * x + 1]);
		 x /= 2;
	 }
}
int query(int a, int b)
{
	if(b < a) return 0;
	a += M;
	b += M;
	
	int w = max(tab[a], tab[b]);
	while(a / 2 != b / 2)
	{
		if(a % 2 == 0) w = max(w, tab[a + 1]);
		if(b % 2 == 1) w = max(w, tab[b - 1]);
		a /= 2;
		b /= 2;
	}
	return w;
}
bool cmp(prostokat a, prostokat b)
{
	return a.x <b.x;
}
int main()
{
	int T,H;
	scanf("%d", &T);
	for (int k=1; k<=T; k++)
	{
		scanf("%d%d", &n, &H);
		int M=1;
		while (M<n) M*=2;
		for (int i=0; i<n; i++)
		{
			int x1,x2,y1,y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			t[i].h=y2-y1;
			t[i].x=x1;
			t[i].pozycja=i;
		}
		sort(t,t+n,cmp);
		for (int i=0; i<n; i++)
		{
			 insert(i,t[i].h);
			 wskaznik[t[i].pozycja]=i;
		 }
		for (int i=0; i<n; i++)
		{
			int x1,x2,y1,y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			wzor[i].pozycja=i;
			wzor[i].x=x1;
		}
		sort(wzor,wzor+n,cmp);
		int test=0;
		for (int i=0; i<n; i++)
		{
			int x=wskaznik[wzor[i].pozycja];
			int ret=query(0,x-1);
			if (t[x].h+ret>H) test =1;
			insert(x,0);
		}
		if (test ==0) printf("TAK\n");
		else printf("NIE\n");
	//	for (int i=0; i<n; ++i) printf("%d %d\n", wskaznik[i], t[i].pozycja);

	}
}