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

using namespace std;

int ileS, ileP, wys, xx1, xy1, xx2, xy2, tab1[50005], tab2[50005], pos[50005], wy[50005], nx[50005], drzewo[131075];
const int L=65536;
bool czynie;
vector <int> w;

struct comp{
	bool operator ()(int const& a, int const& b){
		if(pos[a]>=pos[b]) return true;
		return false;
	}
};

void usunizaktualizuj(int a){
	int v=L+a; drzewo[v]=0;
	while(v!=1){
		v/=2;
		drzewo[v]=max(drzewo[2*v],drzewo[2*v+1]);
	}
}

void inicjuj(int bl){
	for(int i=L+bl; i<=L+L; i++)
		drzewo[i]=0;
	for(int i=L-1; i>0; i--)
		drzewo[i]=max(drzewo[2*i],drzewo[2*i+1]);
}

int maksimum(int a, int b){
	if(a>b) swap(a,b);
	int va=L+a, vb=L+b, m=drzewo[va];
	if(va!=vb) m=max(m,drzewo[vb]);
	while(va/2 != vb/2){
		if(va%2==0) m=max(m,drzewo[va+1]);
		if(vb%2==1) m=max(m,drzewo[vb-1]);
		va/=2; vb/=2;
	}
	return m;
}

int main(){
	scanf("%d", &ileP);
	
	for(int q=0; q<ileP; q++){
	
	scanf("%d %d", &ileS, &wys);
	for(int i=0; i<ileS; i++){
		scanf("%d %d %d %d", &xx1, &xy1, &xx2, &xy2);
		wy[i]=max(xy1,xy2)-min(xy1,xy2);
		tab1[i]=i;
		pos[i]=min(xx1,xx2);
	}
	sort(tab1,tab1+ileS,comp());

	
	for(int i=0; i<ileS; i++){
		nx[tab1[i]]=i;
		drzewo[L+i]=wy[tab1[i]];
		scanf("%d %d %d %d", &xx1, &xy1, &xx2, &xy2);
		tab2[i]=i;
		pos[i]=min(xx1,xx2);
	}
	sort(tab2,tab2+ileS,comp());
	
	inicjuj(ileS);
	czynie=false;
	for(int i=0; i<ileS; i++){
		if(nx[tab2[i]]==0 || wys-maksimum(0,nx[tab2[i]]-1)>=wy[tab2[i]])
			usunizaktualizuj(nx[tab2[i]]);
		else{
			//printf("PROBLEM Z PRZENIESIENIEM SAMOCHODU %d\n",tab2[i]);
			printf("NIE\n");
			czynie=true;
			break;
		}
	}
	if(!czynie)
		printf("TAK\n");
	
	}
}