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
#include<cstdio>
#include<algorithm>
using namespace std;
struct dane{
	long long h,x;
	int i;
}T[100009],D[100009];
int t,n,IND[100009];
long long W;
//Drzewo****************************************
	long long baza[131072];
	void ustal_0(int N){
		for(int i=0;i<N;i++)baza[i+65536]=T[i].h;
	}
	void ustal(){
		for(int i=65535;i>0;i--)baza[i]=max(baza[i*2],baza[i*2+1]);
	}
	
	long long maks(int X){
		X+=65536;
		long long pom=baza[X];
		while(X>1){
			if(X%2==1)pom=max(pom,baza[X-1]);
			X/=2;
		}
		return pom;
	}
	
	void usuni(int X){
		X+=65536;
		baza[X]=-1;
		X/=2;
		while(X>0){
			baza[X]=max(baza[X*2],baza[X*2+1]);
			X/=2;
		}
	}
void czysc(){
	for(int i=0;i<131072;i++)baza[i]=0;
}	
//***********************************************

bool por(dane A,dane B){
	if(A.x<B.x) return 1;
	return 0;
}
int main(){
	long long x_1,y_1,x_2,y_2,przen;
	int pomi;
	scanf("%d",&t);
	while(t--){
		scanf("%d%lld",&n,&W);
		for(int i=0;i<n;i++){
			scanf("%lld%lld%lld%lld",&x_1,&y_1,&x_2,&y_2);
			if(x_1<x_2)T[i].x=x_1; else T[i].x=x_2;
			T[i].h=y_2-y_1;
			T[i].i=i;
			if(T[i].h<0)T[i].h*=-1;
		}
		sort(T,T+n,por);
		
		for(int i=0;i<n;i++){
			scanf("%lld%lld%lld%lld",&x_1,&y_1,&x_2,&y_2);
			if(x_1<x_2)D[i].x=x_1; else D[i].x=x_2;
			D[i].h=y_2-y_1;
			D[i].i=i;
			if(D[i].h<0)D[i].h*=-1;
		}
		sort(D,D+n,por);
		for(int i=0;i<n;i++)IND[T[i].i]=i;
		
		czysc();
		ustal_0(n);
		ustal();
		int ok=1;
		for(int i=0;i<n&&ok;i++){
			pomi=D[i].i;
			usuni(IND[pomi]);
			przen=maks(IND[pomi]);
			if(przen+T[IND[pomi]].h>W)ok=0;
			
		}
		if(ok)printf("TAK\n"); else printf("NIE\n");
		
	}
return 0;
}