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
94
95
96
97
98
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int baum[131072];
int base=65535;
pair< pair<pair<int, int>, pair<int, int> >, pair<pair<int, int>, pair<int, int> > > p[50005];
pair<pair<pair<int, int>, pair<int, int> >, int> tab[50005];
pair<pair<int, int>, pair<int, int> > para;
int wys[50005];
int nr[50005];

void dodaj(int gdzie, int wart)
{
	gdzie=base+gdzie;
	while(gdzie>=1)
	{
		baum[gdzie]=max(baum[gdzie], wart);
		gdzie=gdzie/2;
		}
	}
	
int policz(int pocz, int kon)
{
	pocz=base+pocz;
	kon=base+kon;
	int ret=0;
	while(pocz<kon)
	{
		if(pocz%2==0) pocz=pocz/2;
		else {ret=max(ret, baum[pocz]); pocz=(pocz+1)/2;}
		if(kon%2==1) kon=kon/2;
		else {ret=max(ret, baum[kon]); kon=(kon-1)/2;}
		}
	if(pocz==kon) ret=max(ret, baum[pocz]);
	return ret;	
	}	

int main()
{
	ios_base::sync_with_stdio(0);
	int testy, n, h, acht, maxx, H;
	cin >> testy;
	while(testy--)
	{
		cin >> n >> h;
		for(int i=1; i<=n; i++)
		{
			cin >> p[i].first.first.first >> p[i].first.first.second >> p[i].first.second.first >> p[i].first.second.second;
			if(p[i].first.first.first>p[i].first.second.first) swap(p[i].first.first.first, p[i].first.second.first);
			if(p[i].first.first.second>p[i].first.second.second) swap(p[i].first.first.second, p[i].first.second.second);
			}
		for(int i=1; i<=n; i++)
		{
			cin >> p[i].second.first.first >> p[i].second.first.second >> p[i].second.second.first >> p[i].second.second.second;
			if(p[i].second.first.first>p[i].second.second.first) swap(p[i].second.first.first, p[i].second.second.first);
			if(p[i].second.first.second>p[i].second.second.second) swap(p[i].second.first.second, p[i].second.second.second);
			}	

		sort(p+1,p+n+1);
		for(int i=1; i<=n; i++)
		{
			wys[i]=p[i].first.second.second-p[i].first.first.second;
			para=p[i].second;
			tab[i]=make_pair(para,i);
			}	
		sort(tab+1,tab+n+1);
		for(int i=1; i<=n; i++)
		{
			nr[i]=tab[i].second;
			//cout << nr[i] << " ";
			}
		
		
		acht=0;
		for(int i=1; i<=n; i++)
		{
			H=wys[nr[i]];
			maxx=policz(nr[i]+1, n);
			//cout << H << " " << maxx << " " << h << endl;
			if(H+maxx>h) acht=5;
			dodaj(nr[i], H);
			}
			
		if(acht==5) cout << "NIE\n";
		else cout << "TAK\n";
		
		for(int i=0; i<=2*base; i++)
		{
			baum[i]=0;
			}	
			
		}
	return 0;
}