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
#include <stdio.h>

#define FOR(ii, ll, uu)  for(int ii##lim = (uu), ii = (ll); ii < ii##lim; ++ii)
#define REP(ii, nn) FOR(ii, 0, nn)

// from stackoverflow
#define getcx getchar_unlocked

inline int giu()
{
	int n = 0;
	int ch=getcx();
	while (ch < '0' || ch > '9')
	{
		ch = getcx();
	}
	while (ch >= '0' && ch <= '9')
		n = (n<<3)+(n<<1) + ch-'0', ch = getcx();
	return n;
}

#define GI (giu())

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

typedef pair<int, int> PII;
#define ST first
#define ND second

int main()
{
	REP(t, GI)
	{
		int n=GI, w=GI;
		vector<PII> cars_pre; cars_pre.reserve(n);
		vector<PII> cars_post; cars_post.reserve(n);
		vector<PII> cars_h; cars_h.reserve(n);
		REP(i, n)
		{
			int x1=GI, y1=GI, x2=GI, y2=GI;
			cars_h.push_back(PII(abs(y1-y2), i));
			cars_pre.push_back(PII(min(x1, x2), max(x1, x2)));
		}
		REP(i, n)
		{
			int x1=GI, y1=GI, x2=GI, y2=GI;
			cars_post.push_back(PII(min(x1, x2), max(x1, x2)));
		}
		sort(cars_h.begin(), cars_h.end(), greater<PII>());
// 		reverse(cars_h.begin(), cars_h.end());
// 		REP(i, n)
// 		{
// 			printf("%d: Car %d(h=%d).\n", i, cars_h[i].ND, cars_h[i].ST);
// 		}
		REP(i, n-1)
		{
			if (cars_h[i].ST + cars_h[i+1].ST <= w)
			{
// 				printf("Car %d(h=%d) & car %d(h=%d) fit! Bye.\n", cars_h[i].ND, cars_h[i].ST, cars_h[i+1].ND, cars_h[i+1].ST);
				goto yes;
			}
			FOR(j, i+1, n)
			{

				if (cars_h[i].ST + cars_h[j].ST <= w)
				{
// 					printf("Car %d(h=%d) & car %d(h=%d) fit...\n", cars_h[i].ND, cars_h[i].ST, cars_h[j].ND, cars_h[j].ST);
					break;
				}
				int car1 = cars_h[i].ND;
				int car2 = cars_h[j].ND;
				if (
					cars_pre[car1].ND <= cars_pre[car2].ST && cars_post[car2].ND <= cars_post[car1].ST
					||
					cars_pre[car2].ND <= cars_pre[car1].ST && cars_post[car1].ND <= cars_post[car2].ST
				)
					goto no;
			}
		}
		yes:
			puts("TAK");
			continue;
		no:
			puts("NIE");
			continue;
	}
	return 0;
}