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 <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>

typedef struct
{
    int p;
    int k;
    int w;
} d_a;

int cmp_keys( const void* a, const void* b )
{
    const d_a* aa = (const d_a*)a;
    const d_a* bb = (const d_a*)b;
    return aa->k - bb->k;
}

int maxi( int a, int b) { if ( a > b ) return a; return b; }
int mini( int a, int b) { if ( a < b ) return a; return b; }

int w;

int solve( int n, int off, d_a *data, d_a * res )
{
    /*printf("%d %d %d\n",off, off + n,off);*/
    if ( n <= 1 ) return 1;
    if ( n == 2 )
    {
        if ( data[0].p < data[1].p ) return 1;
        else return data[0].w + data[1].w <= w;
    }
    else
    {
        d_a *bl, *eh;
        int cmax = 0, i, cl, ch, m = n/2 + off;
        /*printf("%d ", m);
        for ( i = 0; i < n; ++i ) 
            printf("%d ",data[i].p);*/
        
        bl = res;
        eh = res + n - 1;
        cl = 0;
        ch = 0;
        for ( i = 0; i < n; ++i )
        {
            if ( data[i].p < m )
            {
                if ( data[i].w + cmax > w ) return 0;
                bl[cl++] = data[i];
            }
            else
            {
                if ( data[i].p > m )
                {
                    (*eh) = data[i];
                    eh--;
                    ch++;
                }
                else if ( data[i].w + cmax > w ) return 0;
                if ( data[i].w > cmax ) cmax = data[i].w;
            }
        }
        /*printf("%d %d\n",cl,ch);*/
        return solve( cl, off, bl, data ) &&
               solve( ch, m + 1, eh, data + cl );
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, i;
        d_a *data, *res;
        scanf( "%d%d", &n, &w );
        data = malloc( sizeof(d_a) * n );
        res = malloc( sizeof(d_a) * n );
        for ( i = 0; i < n; ++i )
        {
            int x1, y1, x2, y2;
            scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
            data[i].k = maxi(x1,x2);
            data[i].w = maxi(y1-y2,y2-y1);
        }
        for ( i = 0; i < n; ++i )
        {
            int x1, y1, x2, y2;
            scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
            data[i].p = mini(x1,x2);
        }
        qsort( data, n, sizeof(d_a), cmp_keys );
        memcpy( res, data, n*sizeof(d_a) );
        for ( i = 0; i < n; ++ i )
        {
            res[i].k = res[i].p;
            res[i].w = i;
        }
        qsort( res, n, sizeof(d_a), cmp_keys );
        for ( i = 0; i < n; ++ i )
        {
            data[ res[i].w ].p = i;
        }
        if ( solve( n, 0, data, res ) ) printf( "TAK\n" );
        else printf( "NIE\n" );
        free(data);
        free(res);
    }
    return 0;
}