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
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

struct Car {
  int id;
  int h;
  int x, y;

  bool operator < (const Car& c) const {
    if (x == c.x) {
      return y < c.y;
    }
    return x < c.x;
  }
};

const int MX = 50005;

int n, H;
Car cars[2][MX];
int pi[MX];
int sigma[MX];

const int M = 1 << 16;
int tree[2*M];

void init() {
  memset(tree, 0, sizeof(tree));
}

void put(int u, int val) {
  u += M;
  while (u) {
    tree[u] = max(tree[u], val);
    u /= 2;
  }
}

int get(int u, int v) {
  if (u > v) return 0;
  u += M;
  v += M;
  if (u == v) return tree[u];
  int res = max(tree[u], tree[v]);
  while (u/2 != v/2) {
    if (u % 2 == 0) res = max(res, tree[u+1]);
    if (v % 2 == 1) res = max(res, tree[v-1]);
    u /= 2;
    v /= 2;
  }
  return res;
}

void tc() {
  scanf("%d%d", &n, &H);
  for (int p = 0; p < 2; ++p) {
    for (int i = 0; i < n; ++i) {
      int x1, y1, x2, y2;
      scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      cars[p][i].id = i;
      if (x1 > x2) {
        swap(x1, x2);
      }
      if (y1 > y2) {
        swap(y1, y2);
      }
      cars[p][i].x = x1;
      cars[p][i].y = y1;
      cars[p][i].h = y2 - y1;
    }
    sort(cars[p], cars[p] + n);
  }
  for (int i = 0; i < n; ++i) {
    pi[cars[0][i].id] = i;
  }
  for (int i = 0; i < n; ++i) {
    cars[1][i].id = pi[cars[1][i].id];
    sigma[cars[1][i].id] = i;
  }
  init();
  for (int i = n-1; i >= 0; --i) {
    int j = sigma[i];
    int mx = get(0, j-1);
    if (mx + cars[1][j].h > H) {
      printf("NIE\n");
      return;
    }
    put(j, cars[1][j].h);
  }
  printf("TAK\n");
}

int main() {
  int ntc;
  scanf("%d", &ntc);
  while (ntc--) tc();
  return 0;
}