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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <random>
#include <cstdlib>

template<typename T> inline void checkmin(T &a, T b){ if(a>b) a = b; }
template<typename T> inline void checkmax(T &a, T b){ if(a<b) a = b; }

#define REP(i,n) for(int i=0; i<(n); ++i)
#define FORD(i,p,k) for(int i=(p); i>=(k); --i)

std::mt19937 rnd(7623423);

struct Car { int y,xa,xb; };

enum { n_max = 50000 };

struct In
{
  int w;
  std::vector<Car> C;
  
  void read()
  {
    int n; scanf("%d%d",&n,&w); C.resize(n);
    int x1,y1,x2,y2;
    REP(i,n)
    {
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      C[i].y = std::abs(y2-y1); C[i].xa = std::min(x1,x2);
    }
    REP(i,n)
    {
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      C[i].xb = std::min(x1,x2);
    }
  }

  void gen(int n = 20)
  {
    w = 10;
    unsigned int x = 1000000000;
    C.resize(n);
    REP(i,n) C[i] = Car{int(rnd()%w),int(rnd()%x),int(rnd()%x)};
  }

  void print()
  {
    printf("n=%d; w=%d\n",C.size(),w);
    for(auto &c : C) printf("y=%d; xa=%d; xb=%d\n",c.y,c.xa,c.xb);
  }
};

bool cmp_a(const Car &a, const Car &b){ return a.xa<b.xa; }
bool cmp_b(const Car &a, const Car &b){ return a.xb<b.xb; }

struct Tree
{
  Tree(int w) : T(w+1) {}
  std::vector<int> T;
  
  void update(int x, int v)
  { while(x<T.size()){ checkmax(T[x],v); x += x&-x; } }
  
  int get(int x)
  {
    int res = 0;
    while(x){ checkmax(res,T[x]); x -= x&-x; }
    return res;
  }
};

bool go(const In &I)
{
  int n = I.C.size();
  std::vector<Car> C(I.C.begin(),I.C.end());
  std::sort(C.begin(),C.end(),cmp_a); REP(i,n) C[i].xa = i+1;
  std::sort(C.begin(),C.end(),cmp_b);
  Tree T(n);
  FORD(i,n-1,0)
  {
    if(T.get(C[i].xa)+C[i].y>I.w) return 0;
    T.update(C[i].xa,C[i].y);
  }
  return 1;
}

bool brute(const In &I)
{
  int n = I.C.size();
  REP(i,n) REP(j,n) if(i!=j && I.C[i].y+I.C[j].y>I.w &&
    (I.C[i].xa<I.C[j].xa ^ I.C[i].xb<I.C[j].xb)) return 0;
  return 1;
}

void test()
{
  REP(_,20){ In I; I.gen(n_max); go(I); }
  puts("max tests done");
  for(int c=0,yes=0;;c++)
  {
    In I; I.gen();
    bool s = go(I);
    bool b = brute(I);
    if(s^b)
    {
      printf("ERROR: s=%d; b=%d\n",s,b);
      I.print();
      exit(1);
    }
    yes += s;
    if(!(c%10000)) printf("ok %d; yes=%d\n",c,yes);
  }
}

int main()
{
  //test();
  int t; scanf("%d",&t);
  while(t--)
  {
    In I; I.read();
    if(go(I)) puts("TAK"); else puts("NIE");
  }

  return 0;
}