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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int i, n, t, w;
int nr_przed[500001];
bool mozna;
const int BASE=524288;
struct S{
	int x1,y1,x2,y2, nr;
};
S sam[500001],sam_przed[500001];
bool op (S a, S b){
	if (a.x1 < b.x1) return true;
	if (a.x1 == b.x1 && ((a.y2 - a.y1) > (b.y2 - b.y1))) return true;
	return false; 
}

int tab[2*BASE];
void dodaj(int nr,int wys ){
     int p=BASE+nr;
     while(p>0){
                tab[p]=max(tab[p],wys);
                p=p/2;
                }
     }
void usun(int nr, int wys){
     int p=BASE+nr;
     tab[p] = 0;
     while(p>1){
                if(p%2==0) tab[p/2] = max(tab[p],tab[p+1]);
                if(p%2==1) tab[p/2] = max(tab[p],tab[p-1]);
                p=p/2;
                }
     }
int maksimum(int a, int b){
    a=a+BASE;
    b=b+BASE;
    int wyn=0;
    wyn =tab[a];
    if (a!=b) wyn = max(wyn,tab[b]);
    while(a/2!=b/2){
                    if(a%2==0) wyn = max(wyn,tab[a+1]);
                    if(b%2==1) wyn = max(wyn,tab[b-1]);
                    a/=2;
                    b/=2;
                    }
    return wyn;
}

void wypisz();
void wypisz2();
int main() {
 scanf("%d",&t);
 while(t--) {
	scanf("%d %d",&n,&w);
	for(i = 0;i < 2*BASE; i++) tab[i] = 0;
	for(i = 0; i < n; ++i){
		scanf("%d%d%d%d",&sam_przed[i].x1,&sam_przed[i].y1,&sam_przed[i].x2,&sam_przed[i].y2);
		sam_przed[i].nr = i;
	   }
	   sort (sam_przed, sam_przed + n, op);
	   for(i = 0; i < n; ++i){
		   dodaj(i,sam_przed[i].y2-sam_przed[i].y1);
		   nr_przed[sam_przed[i].nr] = i;
	   }
	  
	for(i = 0; i < n; ++i){
		scanf("%d%d%d%d",&sam[i].x1,&sam[i].y1,&sam[i].x2,&sam[i].y2);
		sam[i].nr = i;
	   }     
	sort (sam, sam + n, op);
	mozna = true;	
	for(i = 0; i < n; ++i) {
		int WYS = sam[i].y2- sam[i].y1 , NR = sam[i].nr;
		usun(nr_przed[NR], WYS);		
		if(nr_przed[NR] > 0 && maksimum(0, nr_przed[NR]-1) + WYS > w) {
			printf("NIE\n");
			mozna = false;
			break;
		}
		

	}
	if (mozna) printf("TAK\n");
}


return 0;
}