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
#include <cstdio>
#include <algorithm>
using namespace std;
struct str_pom{
	int x,h;
	str_pom (int a=0, int b=0): x(a), h(b) {}
} pom[50010];
struct str{
	int x,h,end_x,i;
	str (int a=0, int b=0, int c=0, int d=0): x(a), h(b), end_x(c), i(d){}
} t[50010];
bool cmp_x(str i, str j){ return (i.x-j.x)? i.x<j.x : i.h>j.h;}
bool cmp_end_x(str i, str j){ return (i.end_x-j.end_x)? i.end_x<j.end_x : i.h>j.h; }
int z,n,w,czapa,d[1300010];
void insert(int a, int w){
	a+=czapa-1;
	d[a]=max(d[a],w);
	for (a=a/2; a; a/=2)
		d[a]=max(d[2*a],d[2*a+1]);
	return;				
}
int query(int a, int b){
	a+=czapa-1;
	b+=czapa-1;
	int res=max(d[a],d[b]);
	for (; a/2!=b/2; a/=2, b/=2){
		if (a%2==0) res=max(res,d[a+1]);
		if (b%2==1) res=max(res,d[b-1]);
	}
	return res;
}
int main(){
	scanf("%d", &z);
	while (z--){
		scanf("%d%d", &n, &w);
		for (int i=0; i<n; ++i){
			int a,b,c,d;
			scanf("%d%d%d%d", &a, &b, &c, &d);
			pom[i]=str_pom(min(a,c),max(b,d)-min(b,d));
		}
		for (int i=0; i<n; ++i){
			int a,b,c,d;
			scanf("%d%d%d%d", &a, &b, &c, &d);
			t[i]=str(pom[i].x,pom[i].h,min(a,c),i+1);
		}
		//przeskalowanie współrzędnych
		sort(t,t+n,cmp_end_x);
		for (int i=0; i<n; ++i) t[i].end_x=i+1;
		sort(t,t+n,cmp_x);
		for (int i=0; i<n; ++i) t[i].x=i+1;
		
		
		
		//przygotowanie drzewa
		for (czapa=1; czapa<=n; czapa*=2);
		for (int i=0; i<=2*czapa; d[i++]=0);
		//odczytywanie wartości z przedziałów i wrzucanie na drzewo
		bool res=true;
		for (int i=0; i<n && res; ++i){
			if (query(min(t[i].x,t[i].end_x),max(t[i].x,t[i].end_x))+t[i].h>w)
				res=false;
			insert(t[i].end_x,t[i].h);
		}
		printf((res)?"TAK\n":"NIE\n");
	}
	return 0;
}