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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;



// ***********************************************************************

int H;
vector<int> M;

void init(vector<int> &P){

    // Przygotuj drzewo
    int n = 1; H = 1;
    while (n<P.size()){ n*=2; ++H; }
    M.resize((1<<H), 0);

    // Wypelnij i zainicjalizuj drzewo
    for(int i=0; i<P.size(); ++i) M[M.size()/2+i] = P[i];
    for(int i=M.size()/2-1; i>=1; --i) M[i]=max(M[2*i], M[2*i+1]);

}

void clear(int k){
    int pos = M.size()/2+k;
    M[pos] = 0; pos /= 2;
    while (pos!=0){
        M[pos] = max(M[pos*2], M[pos*2+1]);
        pos /= 2;
    }
}

int get_max(int k){
    int pos = M.size()/2+k;
    int result = M[pos];
    while (pos!=1){
        if (pos%2) result = max(result, M[pos-1]);
        pos /= 2;
    }
    return result;
}

// ***********************************************************************


int z, n, h;
int X1, Y1, X2, Y2;
vector<int> W;
vector<pair<int,int> > P1, P2;


int main(){

    scanf("%d", &z);
    while(z--){

        // Wczytywanie danych
        scanf("%d %d", &n, &h);
        W.resize(n); P1.resize(n); P2.resize(n);
        for(int i=0; i<n; ++i){
            scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);
            W[i]=abs(Y2-Y1);
            P1[i]=make_pair(min(X1, X2), i);
        }
        for(int i=0; i<n; ++i){
            scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);
            P2[i]=make_pair(min(X1, X2), i);
        }

        // Preprocessing
        sort(P1.begin(), P1.end());
        sort(P2.begin(), P2.end());
        vector<int> P(n); for(int i=0; i<n; ++i) P[i]=W[P1[i].second];
        vector<int> pos_in_P(n); for(int i=0; i<n; ++i) pos_in_P[P1[i].second] = i;
        init(P);

        // Algorytm
        bool ok = true;
        for(int i=0; i<n; ++i){
            int id = P2[i].second;
            int max_h = (pos_in_P[id]==0 ? 0 : get_max(pos_in_P[id]-1));
            if (max_h + W[id] > h){ ok = false; break; }
            clear(pos_in_P[id]);
        }

        if (ok) printf("TAK\n"); else printf("NIE\n");
    }
}