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
#include <cstdio>
#include <algorithm>
#include <memory.h>

using namespace std;

int D[150005];
int P[2][50004];
int L[2][50004];
int P2_rev[50004];
int H[50004];

int size;

void update_up( int e )
{
    while ( e )
        {
            int _e = e>>1;
            if ( D[_e] < D[e] )
                 D[_e] = D[e];
               else return;
            e=_e;
        }
}

int get_p( int p )
{
    p+=size;
    int w = D[p];
    while ( p )
      {
          if (!( p%2 )) w = max( w, D[p+1] );
          p>>=1;
      }
    return w;
}

void set_p( int a, int l )
{
    a+=size;
    D[ a ] = l;
    update_up( a );
}

bool sort_func1( int i, int j )
{ return L[0][i]<L[0][j]; }

bool sort_func2( int i, int j )
{ return L[1][i]<L[1][j]; }

int main()
{
    int ttt;
    scanf("%d",&ttt);
    while ( ttt-- )
       {
           int n,w;
           scanf("%d%d",&n,&w);
           
           size=1; while ( size < n ) size *= 2;
           memset( D, '\0', ((size*2)+1)*4 );
           
           for ( int i=0; i<n; i++)
               {
                   P[0][i]=P[1][i]=i;
                   
                   int x1,y1,x2,y2;
                   scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                   
                   L[0][i]=min( x1, x2 );
                   H[i]=abs( y1-y2 );
                   //printf("%d\n",H[i]);
               }
           
           for ( int i=0; i<n; i++)
               {
                   int x1,y1,x2,y2;
                   scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                   
                   L[1][i]=min( x1, x2 );
               }
           
           sort( P[0],P[0]+n, sort_func1 );
           sort( P[1],P[1]+n, sort_func2 );
           
           for ( int i=0; i<n; i++ )
               P2_rev[P[1][i]]=i;
           
           for ( int i=0; i<n; i++ )
               {
                   int s  = P[0][i];
                   int p2 = P2_rev[ s ];
                   int h  = H[ s ];
                   
                   if ( get_p( p2 ) > w-h )
                       goto _fail;
                   
                   set_p( p2, h );
               }
               
           printf("TAK\n");
           goto _end;
           
           _fail:;
           printf("NIE\n");
           
           _end:;
       }
    
    return 0;
}