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
96
97
#include <iostream>
using namespace std;

class Dzik {
public:
	int numer;
    int x1;
    int y1;
    int x2;
    int y2;
    int wysokosc;
    bool l;
public:
	void wstaw (int nr,int a,int b,int c,int d) {
		numer=nr;
		x1=a; y1=b; x2=c; y2=d;
		wysokosc=y2-y1;
	}

};


int podzial (int l, int p,Dzik tab[]) {
    int i=l-1;
    Dzik x=tab[p];
    Dzik a;
    for (int j=l;j<p;j++)
        if (tab[j].x1<=x.x1) {
            i=i+1;
            a=tab[i];
            tab[i]=tab[j];
            tab[j]=a;
        }
    a=tab[i+1];
    tab[i+1]=tab[p];
    tab[p]=a;
  return i+1;
}

void Quick_sort (int lewy, int prawy, Dzik tab[]){
    if (lewy<prawy) {
        int q=podzial(lewy,prawy,tab);
        Quick_sort(lewy,q-1,tab);
        Quick_sort(q+1,prawy,tab);
    }
}



int main() {
	ios_base::sync_with_stdio (0);
    int t,n=50000,w,a,b,c,d,j;
    bool p;
    Dzik pocz[50000], kon[50000];

    cin>>t;
    while (t--) {
    	cin>>n>>w;
    	p=0;

    	for (int i=0;i<n;i++) {
    		cin>>a>>b>>c>>d;
    		pocz[i].wstaw(i,a,b,c,d);
    	}
    	for (int i=0;i<n;i++) {
    		cin>>a>>b>>c>>d;
    		kon[i].wstaw(i,a,b,c,d);
    		if (kon[i].x1<pocz[i].x1) kon[i].l=1;
    		else pocz[i].l=0;
    	}

    	Quick_sort(0,n-1,kon);
    	Quick_sort(0,n-1,pocz);

    	for (int i=0;i<n;i++) if (kon[i].l) {
            if (p) break;
            for (int a=n-1;a>-1;a--) if (pocz[a].numer==kon[i].numer){
                j=a;
                break;
            }

            while (pocz[j].x1>=kon[i].x1 && j>-1 ) {
                if (pocz[j].wysokosc+kon[i].wysokosc>w) {
                    p=1;
                    break;
                }
                j--;
            }
        }

        if (p) cout<<"NIE"<<endl;
        else cout<<"TAK"<<endl;

    }

    return 0;
}