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
#include <iostream>
#include <algorithm>

const int M = 50000;

inline int left(int p){ return 2*p; }
inline int right(int p){ return 2*p+1; }
inline int parent(int p){ return p/2; }

class T
{
public:
 int t[M*2*2+100];
 int m;
 void drzewify()
 {
  int e = m;
  int p = m;
  while(p=parent(p))
  {
   for(int i=p;i<e;i++)
    t[i] = std::max(t[left(i)],t[right(i)]);
   e = p;
  }
 }
 int get(int start,int end)
 {
  return get(start,end,1,1,m);
 }

 int get(int start,int end,int x,int l,int p)
 {
  //std::cerr << "get("<<start<<", "<<end<<", "<<x<<", "<<l<<", "<<p<<");"<<std::endl;
  if(start == l && end == p)
   return t[x];
  int d = (l+p)/2;
  if(end <= d)
   return get(start,end,left(x),l,d);
  if(start > d)
   return get(start,end,right(x),d+1,p);
  return std::max(get(start,d,left(x),l,d),get(d+1,end,right(x),d+1,p));
 }

 void del(int x)
 {
  x += m-1;
  t[x] = 0;
  while(x=parent(x))
   t[x] = std::max(t[left(x)],t[right(x)]);
 }
};

T t;

typedef struct
{
 int ord1;
 int x1;
 int x2;
 int w;
} U;

U u[M+1];

bool cmp1(const U &a, const U &b) { return a.x1 < b.x1; }
bool cmp2(const U &a, const U &b) { return a.x2 < b.x2; }




bool run()
{
 int n,w;
 int m;
 std::cin >> n >> w;
 m = 2*n-1;
 while(m & (m-1)) m &= m-1;

 t.m = m;
 int x1,x2,y1,y2;
 for(int i=0; i<n; i++)
 {
  std::cin >> x1 >> y1 >> x2 >> y2;
  u[i].x1 = std::min(x1,x2);
  u[i].w = std::abs(y1-y2);
 }
 for(int i=0; i<n; i++)
 {
  std::cin >> x1 >> y1 >> x2 >> y2;
  u[i].x2 = std::min(x1,x2);
 }

 if(n==1)
  return true;

 std::sort(u,u+n,cmp1);
 for(int i=0; i<n; i++)
 {
  u[i].ord1 = i+1;
  t.t[m+i] = u[i].w;
 }
 t.drzewify();
 std::sort(u,u+n,cmp2);
 for(int i=0; i<n; i++)
 {
  /*std::cerr << "samochod " << u[i].ord1 << std::endl;
  if(u[i].ord1 != 1)
   std::cerr << t.get(1,u[i].ord1-1) << std::endl;*/
  if(u[i].ord1 != 1 && u[i].w+t.get(1,u[i].ord1-1)>w)
   return false;
  t.del(u[i].ord1);
 }
 return true;
}

int main()
{
 int t;
 std::cin.sync_with_stdio(false);
 std::cin >> t;
 while(t--)
  std::cout << (run() ? "TAK" : "NIE") << std::endl;
 return 0;
}