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

using namespace std;

struct ParkedCar
{
    int x1, x2, y1, y2;
    int ix;
};

#define max(a,b) ((a)>(b) ? (a) : (b))

const int k = 65536;

ParkedCar cars[50000];
ParkedCar* pcars[50000];

int h[131073];

int sortf(ParkedCar* pc1, ParkedCar* pc2)
{
    return pc1->x1 == pc2->x1 ? pc1->y1 < pc2->y1 : pc1->x1 < pc2->x1;
}

int main(){

int t;
scanf("%i", &t);
for(;t!=0; --t)
{
    int n, w;
    scanf("%i %i", &n, &w);

    for(int i=0; i < n; ++i)
    {
        scanf("%i %i %i %i", &(cars[i].x1), &(cars[i].y1),&(cars[i].x2),&(cars[i].y2));
        if(cars[i].x1 > cars[i].x2)
            swap(cars[i].x1,cars[i].x2);
        if(cars[i].y1 > cars[i].y2)
            swap(cars[i].y1,cars[i].y2);
        pcars[i] = cars+i;
    }

    sort(pcars,pcars+n, sortf);
    memset(h, 0, sizeof(h));

    for(int i=0; i < n; ++i)
    {
        pcars[i]->ix = i;
        h[k+i] = pcars[i]->y2 - pcars[i]->y1;
    }

//for(int i =0 ; i < n; ++i){ printf("%i ", cars[i].ix);}

    int NN = k+n, nn = k;

    while( NN > nn)
    {
        NN>>=1; nn>>=1;
        for(int i = nn; i <= NN;++i)
        {
            h[i] = max(h[i<<1], h[(i<<1)+1]);
        }
    }

    int root = nn;


    for(int i=0; i < n; ++i)
    {
        scanf("%i %i %i %i", &(cars[i].x1), &(cars[i].y1),&(cars[i].x2),&(cars[i].y2));
        if(cars[i].x1 > cars[i].x2)
            swap(cars[i].x1,cars[i].x2);
        if(cars[i].y1 > cars[i].y2)
            swap(cars[i].y1,cars[i].y2);
        pcars[i] = cars+i;
    }

    sort(pcars,pcars+n, sortf);

    for(int i = n-1;  i>= 0; --i)
    {
        int j = k+pcars[i]->ix;
        int H = h[j];
        h[j] = 0;
        while(j != root)
        {
            if( j%2 == 0 && h[j+1]+H > w)
            {
                printf("NIE\n");
                goto NextT;
            }
            j = j>>1;
            h[j] = max(h[j<<1], h[(j<<1)+1]);
        }
    }
    printf("TAK\n");
    NextT: ;
}
return 0;
}