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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>

using namespace std;

struct Size{
    long long int x1;
    long long int y1;
    long long int x2;
    long long int y2;
    long long int onX1;
    long long int onY1;
    long long int onX2;
    long long int onY2;
};

void mergee( int pocz, int sr, int kon, Size *tab, Size *tPom );
void mergesort( int pocz, int kon, Size *tab, Size *tPom );

int main(){
    ios_base::sync_with_stdio(0);

    int t;
    cin>>t;

    for( int i = 0; i < t; ++i ){
        long long int n, w;
        cin>>n>>w;

        Size *place = new Size[n];

        for( int j = 0; j < n; ++j ){
            long long int a, b, c, d;
            cin>>a>>b>>c>>d;
            place[j].x1 = a;
            place[j].y1 = b;
            place[j].x2 = c;
            place[j].y2 = d;
        }

        for( int j = 0; j < n; ++j ){
            long long int a, b, c, d;
            cin>>a>>b>>c>>d;
            place[j].onX1 = a;
            place[j].onY1 = b;
            place[j].onX2 = c;
            place[j].onY2 = d;
        }

        Size *pom = new Size [n];
        mergesort( 0, n-1, place, pom );
        bool result = true;

        for( int j = 1; j < n; ++j ){
            long long int height = place[j].onY2 - place[j].onY1;
            int z = j - 1;

            while( z >= 0 ){
                if( place[j].onX1 < place[z].onX1 ){
                    if( place[z].onY2 - place[z].onY1 + height > w ){
                        result = false;
                        z = 0;
                    }
                }
                --z;
            }
            if( !result ){
                j = n;
            }
        }

        if( result ){
            cout<<"TAK\n";
        }
        else{
            cout<<"NIE\n";
        }

        delete [] pom;
        delete [] place;
    }
}

void mergee( int pocz, int sr, int kon, Size *tab, Size *tPom ){
    int i,j,q;
    for( i = pocz; i <= kon; ++i ){
        tPom[i] = tab[i];
    }
    i = pocz;
    j = sr + 1;
    q = pocz;
    while( i <= sr && j <= kon ){
        if( tPom[i].x1 < tPom[j].x1 ){
            tab[q++] = tPom[i++];
        }
        else{
            tab[q++] = tPom[j++];
        }

    }
    while( i <= sr ){
        tab[q++] = tPom[i++];
    }
}

void mergesort( int pocz, int kon, Size *tab, Size *tPom ){
    int sr;
    if( pocz < kon ){
        sr = ( pocz + kon ) / 2;
        mergesort( pocz, sr, tab, tPom );
        mergesort( sr + 1, kon, tab, tPom );
        mergee( pocz, sr, kon, tab, tPom );
    }
}