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
// Author: Artur Hibner
#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>

using namespace std;

struct samochod {
  int index;
  int pos_pocz;
  int pos_kon;
  int xx1, xx2;
  int yy1, yy2;
};

struct less_xx1_yy1 : public binary_function<samochod, samochod, bool> {
  bool operator()(const samochod &x, const samochod &y) const { return x.xx1 < y.xx1 || (x.xx1 == y.xx1 && x.yy1 < y.yy1); }
};

vector<samochod> samochody_pocz;
vector<samochod> samochody_kon;
samochod sam;
int t, n, w, xx1, xx2, yy1, yy2;
int poz_pocz[65536], poz_kon[65536], wys[65536];

int main() {
  scanf("%d", &t);
  for (int i = 0 ; i < t ; i++) {
    scanf("%d%d", &n, &w);
    samochody_pocz.clear();
    for (int j = 0 ; j < n ; j++) {
      scanf("%d%d%d%d", &xx1, &yy1, &xx2, &yy2);
      if (xx1 > xx2) { sam.xx1 = xx2; sam.xx2 = xx1; }
      else { sam.xx1 = xx1; sam.xx2 = xx2; }
      if (yy1 > yy2) { sam.yy1 = yy2; sam.yy2 = yy1; }
      else { sam.yy1 = yy1; sam.yy2 = yy2; }
      sam.index = j;
      samochody_pocz.push_back(sam);
    }
    sort(samochody_pocz.begin(), samochody_pocz.end(), less_xx1_yy1());
    samochody_kon.clear();
    for (int j = 0 ; j < n ; j++) {
      scanf("%d%d%d%d", &xx1, &yy1, &xx2, &yy2);
      if (xx1 > xx2) { sam.xx1 = xx2; sam.xx2 = xx1; }
      else { sam.xx1 = xx1; sam.xx2 = xx2; }
      if (yy1 > yy2) { sam.yy1 = yy2; sam.yy2 = yy1; }
      else { sam.yy1 = yy1; sam.yy2 = yy2; }
      sam.index = j;
      samochody_kon.push_back(sam);
    }
    sort(samochody_kon.begin(), samochody_kon.end(), less_xx1_yy1());
    for (int j = 0 ; j < n ; j++) {
      poz_pocz[samochody_pocz[j].index] = j;
      poz_kon[samochody_kon[j].index] = j;
      wys[samochody_pocz[j].index] = samochody_pocz[j].yy2 - samochody_pocz[j].yy1;
    }
    bool ok = true;
    for (int j = 0 ; j < n ; j++) {
      for(int k = j+1 ; k < n ; k++) {
        if((poz_pocz[j] < poz_pocz[k]) && (poz_kon[j] > poz_kon[k]) ||
           (poz_pocz[j] > poz_pocz[k]) && (poz_kon[j] < poz_kon[k])) {
          if (wys[j] + wys[k] > w) {
            ok = false;
            k = n;
            j = n;
          }
        }
      }
    }
    if (ok) {
      printf("TAK\n");
    } else {
      printf("NIE\n");
    }
  }
  return 0;
}