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
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define mp make_pair

struct car
{
	int x1, x2, y1, y2, nr;
	
	void read(int number)
	{
		nr = number;
		scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
		if ( x2 < x1 ) swap(x1,x2);
		if ( y2 < y1 ) swap(y1,y2);
	}
	
	bool operator< (const car& A) const
	{
		return mp( mp(x1,y1), mp(x2,y2) ) < mp( mp(A.x1,A.y1), mp(A.x2,A.y2) );
	}
	
	int height() const { return y2-y1; }
};

int shift;
vector<int> T, W;

int maximum(int x)
{
	if (x<0) return -1;
	x += shift;
	int ans = T[x];
	while(x>1)
	{
		if ( x%2==1 ) ans = max( ans, T[x-1] );
		x = x/2;
	}
	return ans;
}

void insert(int x, int val)
{
	x += shift;
	T[x] = val;
	x = x/2;
	while (x>0)
	{
		T[x] = max( T[2*x], T[2*x+1] );
		x = x/2;
	}
}

bool solve()
{
	int n, H;
	scanf("%d%d", &n, &H);
	vector<car> A(n), B(n);
	
	shift = 1; while ( shift<=n ) shift <<= 1;
	T.resize(0); T.resize( 2*shift+1, -1 );
		
	for (int i=0; i<n; i++) A[i].read(i); sort(A.begin(), A.end());
	for (int i=0; i<n; i++) B[i].read(i); sort(B.begin(), B.end());
	
	W.resize(n);
	for (int i=0; i<n; i++)
	{
		insert(i, A[i].height()); 
		W[ A[i].nr ] = i;
	}
	
	// sprawdzamy czy najwyższe auto, które znajduje się na lewo od b
	// pozwoli przejechać mu na sam początek (na lewo)
	// jeśli tak, to usuwamy b.
	for (auto b : B)
		if ( H < maximum(W[b.nr]-1)+b.height() )
			return false;
		else
			insert( W[b.nr] , -1 );
	return true; 
}

int main()
{
	int t; scanf("%d", &t); while(t--) puts( solve() ? "TAK" : "NIE" );
	return 0;
}