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
93
94
95
#include<cstdio>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define F first
#define MP make_pair
#define S second
#define PB push_back
#define LL long long
const int M=1024*64;

struct car
{
	int h, s, i;
};

vector<car> V[2];
int D[2*M], T[M];

void add(int v, int w)
{
	v+=M;
	D[v]=w;
	while(v>1)
	{
		v/=2;
		D[v]=max(D[2*v], D[2*v+1]);
	}
}

int maxi(int p, int k)
{
	if(p>k) return 0;
	p+=M;
	k+=M;
	int res=max(D[p], D[k]);
	while(p/2!=k/2)
	{
		if(p%2==0) res=max(res, D[p+1]);
		if(k%2==1) res=max(res, D[k-1]);
		p/=2;
		k/=2;
	}
	return res;
}

bool cmp(car a, car b)
{
	return a.s<b.s;
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		for(int i=0; i<2*M; i++) D[i]=0;
		for(int i=0; i<2; i++) V[i].clear();
		int n, h;
		bool b=1;
		scanf("%d%d", &n, &h);
		for(int j=0; j<2; j++)
		{
			for(int i=0; i<n; i++)
			{
				int a, b, c, d;
				scanf("%d%d%d%d", &a, &b, &c, &d);
				car x;
				x.s=min(a, c);
				x.h=abs(b-d);
				x.i=i;
				V[j].PB(x);
			}
			sort(V[j].begin(), V[j].end(), cmp);
		}
		for(int i=0; i<n; i++) D[i+M]=V[0][i].h;
		for(int i=M-1; i>0; i--) D[i]=max(D[2*i], D[2*i+1]);
		for(int i=0; i<n; i++) T[V[0][i].i]=i;
		for(int i=0; i<n; i++)
		{
			int x=maxi(0, T[V[1][i].i]-1);
			if(x+V[1][i].h>h)
			{
				b=0;
				break;
			}
			add(T[V[1][i].i], 0);
		}
		if(b) printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}