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

using namespace std;

//Brute Force O(N^2)

struct Rect
{
	int left, right, top, bot;
	int H;
	Rect *des;
	Rect():left(0), right(0), top(0), bot(0), H(0), des(NULL){}
	Rect(int left, int right, int top, int bot):left(left), right(right), top(top), bot(bot), des(NULL), H(top-bot){}
};

const int MAX = 5 * (int)10e4;

Rect TAB[MAX];
Rect DES[MAX];

int main()
{
	int S;
	scanf("%d", &S);
	while(--S>=0){
	try{
	int N, W;
	scanf("%d %d", &N, &W);
	for(int i = 0; i<N; i++)
	{
		int b, t, l, r;
		scanf("%d %d %d %d", &l, &b, &r, &t);
		if(b>t)swap(b,t);
		if(l>r)swap(l,r);
		TAB[i] = Rect(l,r,t,b);
	}
	for(int i = 0; i<N; i++)
	{
		int b, t, l, r;
		scanf("%d %d %d %d", &l, &b, &r, &t);
		if(b>t)swap(b,t);
		if(l>r)swap(l,r);
		DES[i] = Rect(l,r,t,b);
		TAB[i].des = &DES[i];
	}

	for(int i = 0; i<N; i++)
	{
		if(TAB[i].left == TAB[i].des->left) continue;
		int des = W - TAB[i].H;
		for(int j = 0; j<N; j++)
		{
			if(i!=j)
			{
				if(TAB[j].H > des)
				{
					if(TAB[i].des->right >= TAB[i].right) // na prawo
					{
						if(TAB[j].des->right >= TAB[i].right)
						if(TAB[j].des->left <= TAB[i].des->left) throw 0;
					}
					if(TAB[i].des->left <= TAB[i].left) // na lewo
					{
						if(TAB[j].des->left <= TAB[i].left)
						if(TAB[j].des->right >= TAB[i].des->right) throw 0;
					}
				}
			}
		}
	}printf("TAK\n");}
	catch(int code) { printf("NIE\n");}
	}
	return 0;
}