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

//#define DEBUG 1

#ifdef DEBUG
#define debug(x...) printf(x)  
#else
#define debug(x...)  
#endif

inline bool getz(int a)
{
	if (a>=0) return true;
	else return false;
}

struct CRectangle
{
	int x1, x2, height;
	bool operator < (const CRectangle& other) const { return this->height > other.height; }
};

typedef std::vector<CRectangle> Sequence;

Sequence rectangles;

void test_case()
{
	int n, w;
	
	//READ INPUT
	scanf("%d %d", &n, &w);
	
	rectangles.resize(n);
	
	for (int i = 0; i < n; ++i)
	{
		int ax1, ax2, ay1, ay2;
		scanf("%d %d %d %d", &ax1, &ay1, &ax2, &ay2);
		rectangles[i].x1 = std::min(ax1, ax2);
		rectangles[i].height = abs(ay1 - ay2);
	}
	for (int i = 0; i < n; ++i)
	{
		int ax1, ax2, ay1, ay2;
		scanf("%d %d %d %d", &ax1, &ay1, &ax2, &ay2);
		rectangles[i].x2 = std::min(ax1, ax2);
	}
	
	std::sort(rectangles.begin(), rectangles.end());
	
	for (int i = 0; i < n; ++i)
	{
		if ((i+1 < n) && (rectangles[i].height + rectangles[i+1].height <= w))
		{
			printf("TAK\n");
			return;
		}
		for (int j = i+1; j < n; ++j)
		{
			if (rectangles[i].height + rectangles[j].height > w)
			{
				if (getz(rectangles[i].x1 - rectangles[j].x1) != getz(rectangles[i].x2 - rectangles[j].x2))
				{
					debug("Failing ones: %d and %d\n", i, j);
					printf("NIE\n");
					return;
				}
			}
			else break;
		}
	}

	printf("TAK\n");
	return;
}

int main()
{
	int t;
	scanf("%d", &t);
	
	while (t--)
	{
		test_case();
	}
	return 0;
}