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
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;

const int MAXN = (1<<16) + 1;
int CMP_IDX;

struct Car {
  int pos[2];
  int x[2];
  int h[2];
  int w[2];
  void read(int idx) {
    int x1, x2, y1, y2;
    assert(4 == scanf("%d%d%d%d", &x1, &y1, &x2, &y2));
    x[idx] = min(x1, x2);
    w[idx] = max(x1, x2) - min(x1, x2);
    h[idx] = max(y1, y2) - min(y1, y2);
  }

};

Car cars[MAXN];

struct CarPtr {
  int idx;
  bool operator<(const CarPtr& other) const {
    return cars[idx].x[CMP_IDX] < cars[other.idx].x[CMP_IDX];
  }
};

CarPtr ptrs[MAXN];

struct Tree {
  int v[2*MAXN];
  int nn;
  void init(int n) {
    for (nn = 1; nn < n; nn *= 2) continue;
    for (int i = 0; i < nn; ++i) {
      v[i] = 0;
    }
  }
  void set(int idx, int value) {
    idx += nn;
    v[idx] = value;
    idx /= 2;
    while (idx > 0) {
      v[idx] = max(v[2*idx], v[2*idx+1]);
      idx /= 2;
    }
  }
  int get_max(int idx, int vbeg, int vend, int beg, int end) {
    if (end <= beg or end <= vbeg or vend <= beg) {
      return 0;
    }
    if (vbeg + 1 == vend) {
      return v[idx];
    }
    int vmid = (vbeg + vend) / 2;
    return max(get_max(2 * idx, vbeg, vmid, beg, min(vmid, end)),
               get_max(2 * idx + 1, vmid, vend, max(beg, vmid), end));
  }
  int get_max(int beg, int end) {
    return get_max(1, 0, nn, beg, end);
  }
};

Tree t;

int n, w;

bool solve() {
  assert(2 == scanf("%d%d", &n, &w));
  t.init(n);

  for (int idx = 0; idx < 2; ++idx) {
    for (int i = 0; i < n; ++i) {
      cars[i].read(idx);
      ptrs[i].idx = i;
    }
    CMP_IDX = idx;
    sort(ptrs, ptrs + n);
    for (int i = 0; i < n; ++i) {
      cars[ptrs[i].idx].pos[idx] = i;
    }
  }

  for (int i = 0; i < n; ++i) {
    if (cars[i].w[0] != cars[i].w[1] or cars[i].h[0] != cars[i].h[1]) {
      return false;
    }
    t.set(cars[i].pos[0], cars[i].h[0]);
  }

  for (int i = 0; i < n; ++i) {
    int ci = ptrs[i].idx;
    if (w - t.get_max(0, cars[ci].pos[0]) < cars[ci].h[0]) {
      return false;
    }
    t.set(cars[ci].pos[0], 0);
  }
  return true;
}

int main() {
  int z;
  assert(1 == scanf("%d", &z));
  while (z--) {
    if (solve()) printf("TAK\n");
    else printf("NIE\n");
  }
  return 0;
}