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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <utility>
#include <set>
#include <map>
#include <queue>
using namespace std;

#define FOR(x,b,e) for(int x=b; x<=(e); ++x)
#define REP(x,n) for(int x=0; x<(n); ++x)
#define FORD(x,b,e) for(int x=b; x>=(e); --x)
typedef pair<int,int> PII;
#define MP make_pair 
#define MAXN 50005 
#define ST first
#define ND second
int t,n,w;
int H[MAXN];
int X[MAXN];
int E[MAXN];
PII ORD[MAXN];
PII ORD_H[MAXN];
int M[MAXN];

bool isFirstOnLeft(int st, int nd){
  return E[st]<=E[nd];
}

bool merge(int begin, int end){
  if(begin>=end) return true;
  int mid = (begin+end)/2;
  if(!merge(begin,mid)||!merge(mid+1,end))
    return false;
/*
  printf("merge %d %d\n",begin,end);
  FOR(x,begin,end)printf("%d ", ORD[x].ND);
  printf("\n");
  */ 
  FOR(x,begin,end){ORD_H[x].ST=ORD[x].ST; ORD_H[x].ND=ORD[x].ND;}  
  FORD(x,mid,begin)M[x]=0;
  M[mid]=H[ORD_H[mid].ND];
  FORD(x,mid-1,begin)M[x]=max(M[x+1],H[ORD_H[x].ND]);
  FORD(x,end,mid+1)M[x]=0;
  M[end]=H[ORD_H[end].ND];
  FORD(x,end,mid+1)M[x]=max(M[x+1],H[ORD_H[x].ND]);
/*
  FOR(x,begin,end)printf("%d ", M[x]);
  printf("\n");
  FOR(x,begin,end)printf("%d ", H[ORD_H[x].ND]);
  printf("\n");
  FOR(x,begin,end)printf("%d ", E[ORD_H[x].ND]);
  printf("\n");
*/

  int st=begin,nd=mid+1;
  int org=begin;
  while(st<=mid&&nd<=end){
    //printf("st %d nd %d e1 %d e2 %d \n",ORD_H[st].ND,ORD_H[nd].ND,E[ORD_H[st].ND],E[ORD_H[nd].ND]);
    if(E[ORD_H[st].ND]<=E[ORD_H[nd].ND]){
        ORD[org].ST=ORD_H[st].ST;
        ORD[org].ND=ORD_H[st].ND;
      st++;
    } else {
      //printf("War st %d nd %d max %d h %d\n",ORD_H[st].ND,ORD_H[nd].ND,M[st],H[ORD_H[nd].ND]);
      if(M[st]+H[ORD_H[nd].ND]<=w){
        ORD[org].ST=ORD_H[nd].ST;
        ORD[org].ND=ORD_H[nd].ND;
      } else return false;
      nd++;
    }
    org++;
  }  

  while(st<=mid){
    ORD[org].ST=ORD_H[st].ST;
    ORD[org].ND=ORD_H[st].ND;
    st++;
    org++;
  }
  while(nd<=end){
    ORD[org].ST=ORD_H[nd].ST;
    ORD[org].ND=ORD_H[nd].ND;
    nd++;
    org++;
  }
  return true;
}


void solve(){
  /*REP(x,n)printf("(%d,%d) ",X[x],H[x]);
  printf("\n");
  REP(x,n)printf("(%d,%d) ",ORD[x].ST, ORD[x].ND); 
  printf("\n");
  REP(x,n)printf("%d ",E[x]);
  printf("\n");
  */
  if(!merge(0,n-1))
    printf("NIE\n");
  else 
    printf("TAK\n");
}

int main() {
  scanf("%d",&t);
  int x1,y1,x2,y2;
  REP(x,t){
    scanf("%d%d",&n,&w);
    REP(y,n){
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      H[y]=abs(y2-y1);
      X[y]=min(x1,x2);
      ORD[y].ST=min(x1,x2);
      ORD[y].ND=y;
    }
    sort(ORD,ORD+n);
    REP(y,n){
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      E[y]=min(x1,x2);
    }
    solve();  
  }
  
  return 0;
}