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
#include <iostream>
#include <vector>
#include <cmath>
#include <set>

using namespace std;

bool isIntersection(int begin1, int end1, int begin2, int end2) {
  return end1 > begin2 && begin1 < end2;
}

int delta(int end1, int begin2) {
  return end1 - begin2;
}

struct Car {
  Car() {}
  Car (int i, int _x1, int _x2, int y1, int y2)
  : idx(i), x1(_x1), x2(_x2), w(y2 - y1) {}
  
  Car (int i, int _x1, int _x2)
  : idx(i), x1(_x1), x2(_x2){}
  int idx;
  int x1;
  int x2;
  int w;
};

/*struct ComparatorHead {
  bool operator()(const Car& c1, const Car& c2) const {
    return c1.x1 < c2.x1;
  }
};*/

struct ComparatorDiff {
  bool operator()(const Car& c1, const Car& c2) const {
    return c1.w > c2.w;
  }
};

bool test() {
  int n, w, wmax = 0;
  cin >> n >> w;
  int x1, x2, y1, y2;
  multiset<Car, ComparatorDiff> start;

  for (int i = 0; i < n; ++i) {
    cin >> x1 >> y1 >> x2 >> y2;
    start.insert(Car(i, x1, x2, y1, y2));
    if (y2 - y1 > wmax) wmax = y2 - y1;
  }
  
  if (wmax <= w/2) return true; 
  int wbound = w - wmax;
  
  vector<Car> goal(n);
  for (int i = 0; i < n; ++i) {
    cin >> x1 >> y1 >> x2 >> y2;
    goal[i] = Car(i, x1, x2, y1, y2);
  }
  int whalf = w/2;
  for (multiset<Car>::const_iterator i = start.begin(); i != start.end(); ++i) {
    //cout << "i: " << i->idx << " w: " << i->w << endl;
    if (i->w <= whalf) break;
    int wmin = w - i->w;
    for (multiset<Car>::const_iterator j = i; j != start.end(); ++j) {
     // cout << "j: " << j->idx << " w: " << j->w << endl;
      if (j->w <= wmin) break;
      if (!isIntersection(i->x1, i->x2, j->x1, j->x2)) {
	if (i->x1 < j->x1) {
	  //cout << "Norm" << endl;
	  if (goal[j->idx].x1 < goal[i->idx].x2) { // must
	    if (i->w + j->w > w) return false; // can't
	  }
	} else {
	//  cout << "Swap" << endl;
	  if (goal[i->idx].x1 < goal[j->idx].x2) { // must
	    if (i->w + j->w > w) return false; // can't
	  }
	}
      }
    }
  }
  
  return true;
}


int main() {
  cin.sync_with_stdio(false);
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    cout << (test() ? "TAK" : "NIE") << endl;
  }
  return 0;
}