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
#include <cstdio>
#include <iostream>
#include <algorithm>

#define nm long long int
#define unm unsigned long long int
#define uint unsigned int
#define srt(a, b) std::sort((a), (a)+(b))

using namespace std;

//x1 y1 x2 y2
//typedef pair< pair<nm,nm>, pair <nm, nm> > kwadrat;

struct kwadrat {

nm x1;
nm y1;
nm x2;
nm y2;

};

vector< pair<kwadrat,uint> > k,k2;
kwadrat t1;

uint t,n,w;
bool f=0;

bool col(kwadrat a, kwadrat b) {

if(a.x1 < b.x2 && a.x2 > b.x1 &&
   a.y1 < b.y2 && a.y2 > b.y1)
    return 1;
return 0;

}

nm wys(kwadrat a) {
    return abs(a.y2-a.y1);
}

nm szer(kwadrat a){
    return abs(a.x2-a.x1);
}

int main()
{
    scanf("%u", &t);

    for(uint i=0;i<t;i++) {

        scanf("%u %u", &n, &w);
        k.clear();
        k2.clear();
        f=0;
        for(unm j=0;j<n;j++) {
            scanf("%lli %lli %lli %lli", &t1.x1, &t1.y1, &t1.x2, &t1.y2);
            k.push_back(make_pair(t1,j));
        }

        sort(k.begin(), k.end(), [](pair<kwadrat,unm> a, pair<kwadrat,unm> b){ if(a.first.x2!=b.first.x2){return a.first.x2 < b.first.x2;}else{return a.second > b.second;} });

        for(unm j=0;j<n;j++) {
            k[j].second = j;
            scanf("%lli %lli %lli %lli", &t1.x1, &t1.y1, &t1.x2, &t1.y2);
            k2.push_back(make_pair(t1,j));
        }
        sort(k2.begin(), k2.end(), [](pair<kwadrat,unm> a, pair<kwadrat,unm> b){ if(a.first.x2!=b.first.x2){return a.first.x2 < b.first.x2;}else{return a.second > b.second;} });

       /* printf("K:\n");
        for(unm j=0;j<k.size();j++) {
            printf("%u: %lli %lli %lli %lli\n", k[j].second, k[j].first.x1, k[j].first.y1, k[j].first.x2, k[j].first.y2);
        }
        printf("K2:\n");*/
        for(unm j=0;j<k2.size();j++) {
           // printf("%u: %lli %lli %lli %lli\n", k2[j].second, k2[j].first.x1, k2[j].first.y1, k2[j].first.x2, k2[j].first.y2);
            for(unm l=j;l<=k2[j].second;l++) {

                if(wys(k2[j].first)+wys(k2[l].first)>w) {
                f=1;
                //printf("NIE:%llu\n",l);
                }


            }
        }

        if(f)
            printf("NIE\n");
        else
            printf("TAK\n");

    }
    return 0;
}