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

using namespace std;
const int N = 65536;
int n, w;
int x[N], dy[N];
int ord1[N], ord2[N];

class MaxValue {
  public:
  MaxValue() {
    clean();
  }

  void clean() {
    fill_n(t_, N + N, 0);
  }

  void insert(int pos, int v) {
    pos += N;
    t_[pos] = v;
    while (pos) {
      pos /= 2;
      t_[pos] = max(t_[pos * 2], t_[pos * 2 + 1]);
    }
  }

  int get(int a, int b) {
    int ret = 0;
    a += N;
    b += N;
    while (a < b) {
      ret = max(ret, t_[a]);
      if (a + 1 < b) {
        ret = max(ret, t_[a + 1]);
      }
      a = a / 2 + 1;
      ret = max(ret, t_[b - 1]);
      b /= 2;
    }
    return ret;
  }

  private:
  int t_[N + N];
};

bool comp(int a, int b) {
  return x[a] < x[b];
}

void read() {
  for (int i = 0; i < n; ++i) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    ord1[i] = i;
    x[i] = x1;
    dy[i] = y2 - y1;
  }
  sort(ord1, ord1 + n, comp);
}

MaxValue mv;

void solve() {
  scanf("%d%d", &n, &w);
  mv.clean();
  read();
  for (int i = 0; i < n; ++i) {
    ord2[ord1[i]] = i;
    mv.insert(i, dy[ord1[i]]);
  }
  read();
  bool ok = true;
  for (int i = 0; ok && i < n; ++i) {
    const int j = ord1[i];
    const int k = ord2[j];
    const int y = w - dy[j];
    ok = (y >= mv.get(0, k));
    mv.insert(k, 0);
  }
  printf("%s\n", ok ? "TAK" : "NIE");
}

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