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

using namespace std;

class car
{
public:
int x1,x2,y1,y2,n,nx1,nx2,ny1,ny2;
};

bool cmp1(car i, car j)
{
	if (i.x1 == j.x1) return i.y1 < j.y1;
	else return i.x1 < j.x1;
}

bool cmp2(car i, car j)
{
	if (i.nx1 == j.nx1) return i.ny1 < j.ny1;
	else return i.nx1 < j.nx1;
}

int main()
{
int t,T,n,N,w,i,j;
car tmp;
vector< car > x;

	scanf("%d",&T);
	
	for (t = 0; t < T; t++)
	{
		scanf("%d %d",&N,&w);
		for (n = 0; n < N; n++)
		{
			scanf("%d %d %d %d",&(tmp.x1),&(tmp.y1),&(tmp.x2),&(tmp.y2));
			x.push_back(tmp);
		}
		for (n = 0; n < N; n++)
		{
			scanf("%d %d %d %d",&(x[n].nx1),&(x[n].ny1),&(x[n].nx2),&(x[n].ny2));
		}
		
		sort(x.begin(),x.end(),cmp1);
		for (n = 0; n < N; n++) x[n].n = n;
		sort(x.begin(),x.end(),cmp2);
		n = 0;
		for (i = 0; i < N; i++)
		{
			if (x[i].n > i)
			{
				j = i;
				while (x[j].n > j && x[j].y2-x[j].y1+x[j+1].y2-x[j+1].y1 <= w) {tmp = x[j]; x[j] = x[j+1]; x[j+1] = tmp; j++;}
				if (x[j].n > j) break;
			}
		}
				
		if (i == N) printf("TAK\n"); else printf("NIE\n");
	}

	return 0;	
}