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
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef int I;
typedef pair<I, I> P;
typedef vector<I> VI;
typedef vector<P> VP;

struct S {
  I prev, next, curh, maxh;
  S(I p, I n, I c, I m):prev(p), next(n), curh(c), maxh(m) {}
};
typedef vector<S> VS;

inline void updatevalid(I i, VS& vs) {
  I nn = vs.size();
  while (i < nn) {
    I maxh = 0;
    S& cur = vs[i];
    I prev = cur.prev;
    if (prev >= 0) {
      maxh = std::max(vs[prev].maxh, vs[prev].curh); 
    }
    if (cur.maxh == maxh)
      return;
    cur.maxh = maxh;
    i = cur.next;
  }
}

static bool calc(const I w, const VP& v) {
  const I nn = v.size();

  VI lt;
  VS vs;
  lt.reserve(nn);
  vs.reserve(nn);
  I maxh = 0;
  for (I n=0; n<nn; ++n) {
    I h = v[n].second;
    lt[v[n].first] = n;
    vs.push_back(S(n-1, n+1, h, maxh));
    if (h > maxh)
      maxh = h;
  }
  for (I n=0; n<nn; ++n) {
    I i = lt[n];
    const S& s = vs[i];
    if (s.curh + s.maxh > w)
      return false;
    if (s.prev >= 0)
      vs[s.prev].next = s.next;
    if (s.next < nn) {
      vs[s.next].prev = s.prev;
      updatevalid(s.next, vs);
    }
  }

  return true;
}

int main() {
  I tt;
  scanf("%d\n", &tt);
  for (I t=0; t<tt; ++t) {
    I nn, w, x1, y1, x2, y2;
    scanf("%d %d\n", &nn, &w);
    //----
    VP va, vb;
    VI vh;
    va.reserve(nn);
    vb.reserve(nn);
    vh.reserve(nn);
    for (I n=0; n<nn; ++n) {
      scanf("%d %d %d %d\n", &x1, &y1, &x2, &y2);
      I x = x1<x2?x1:x2;
      I h = y1<y2?y2-y1:y1-y2;
      va.push_back(P(x, n));
      vh.push_back(h);
    }
    for (I n=0; n<nn; ++n) {
      scanf("%d %d %d %d\n", &x1, &y1, &x2, &y2);
      I x = x1<x2?x1:x2;
      vb.push_back(P(x, n));
    }
    //---
    std::sort(va.begin(), va.end());
    std::sort(vb.begin(), vb.end());
    VI lut(nn);
    for (I n=0; n<nn; ++n) {
      lut[va[n].second] = n;
    }
    VP ph;
    ph.reserve(nn);
    for (I n=0; n<nn; ++n) {
      I i = vb[n].second;
      I h = vh[i];
      I p = lut[i];
      ph.push_back(P(p, h));
    }
    //---
    if (calc(w, ph))
      printf("TAK\n");
    else
      printf("NIE\n");
  }
  return 0;
}