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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAXN=50000;

typedef struct {
    int i,x,h;
} Car;


struct segtree {
  static const int M = 65536;

  int w[2*M];

  void clear() {
    memset (w, 0, sizeof (w) );
  }

  void insert (int c, int p) {

    int i;
     i=p+M;
     while (i) {
       w[i]+=c;
        i >>= 1;
      }
  }

  int interval_max (int a, int b) {

 int wyn;
     if (a == b) {
        wyn=w[a+M];
     } else {
    a += M;
    b += M;

    wyn=w[a] + w[b];

    while ( (a >> 1) != (b >> 1) ) {
        if (! (a & 1) ) {
            wyn += w[a + 1];
        }

        if (b & 1) {
            wyn += w[b - 1];

        a >>= 1;
        b >>= 1;
      }
     }
     }
    return wyn;
  }

} ST;




Car T[MAXN];
Car *S[MAXN];

bool cmp(const Car *a, const Car *b) {
    return (a->x < b->x);
}

bool test() {
  int n,w,i,x1,x2,y1,y2;

  scanf("%d%d",&n,&w);

  for (i=0; i<n; ++i) {

    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

    T[i].x=min(x1,x2);
    T[i].h=abs(y2-y1);
    S[i]=&T[i];
  }

  sort(S,S+n,cmp);
  ST.clear();

  for (i=0; i<n; ++i) {
    S[i]->i=i;
    ST.insert(i,S[i]->h);

    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

    T[i].x=min(x1,x2);
  }

  sort(S,S+n,cmp);

  for (i=0; i<n; ++i) {
    int d=0;

    if (S[i]->i>i) {
        d=ST.interval_max(i,S[i]->i-1);

    if (w-d<S[i]->h) return false;

  }


        }



  return true;

}

int main()
{

  int t,i;

  scanf("%d",&t);

  while (t--)
    puts(test()? "TAK" : "NIE");

    return 0;
}