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

using namespace std;

struct tSamochod {
  long id, poczatek, wysokosc;
  bool operator<(const tSamochod &rhs) const {
    return poczatek < rhs.poczatek;
  }
};

int main() {
  ios_base::sync_with_stdio(0);

  int t;
  cin >> t;
  for(int i = 0; i < t; ++i) {
    long n, w;
    long x1, y1, x2, y2;
    cin >> n >> w;
    vector<tSamochod> ustPoczatkowe(n);
    vector<long> mapaPoczatkowe(n);
    vector<tSamochod> ustKoncowe(n);
    for(long j = 0; j < n; ++j) {
      cin >> x1 >> y1 >> x2 >> y2;
      ustPoczatkowe[j].id = j;
      ustPoczatkowe[j].poczatek = min(x1, x2);
      ustPoczatkowe[j].wysokosc = max(y1, y2) - min(y1, y2);
    }
    for(long j = 0; j < n; ++j) {
      cin >> x1 >> y1 >> x2 >> y2;
      ustKoncowe[j].id = j;
      ustKoncowe[j].poczatek = min(x1, x2);
      ustKoncowe[j].wysokosc = max(y1, y2) - min(y1, y2);
    }
    if(n == 1) {
      cout << "TAK" << endl;
      continue;
    }
    sort(ustPoczatkowe.begin(), ustPoczatkowe.end());
    sort(ustKoncowe.begin(), ustKoncowe.end());
    for(size_t j = 0; j < ustPoczatkowe.size(); ++j)
      mapaPoczatkowe[ustPoczatkowe[j].id] = j;
    long wezlowDrzewa;
    {
      long ill = n;
      int bitow = -1;
      while(ill > 0) {
        ill /= 2;
        bitow++;
      }
      wezlowDrzewa = 1L << bitow;
      if(wezlowDrzewa < n)
        wezlowDrzewa <<= 1;
    }
    vector<long> drzewo(2 * wezlowDrzewa, 0);
    for(size_t j = 0; j < ustPoczatkowe.size(); ++j)
      drzewo[wezlowDrzewa + j] = ustPoczatkowe[j].wysokosc;
    for(long p = wezlowDrzewa / 2; p > 0; p /= 2)
      for(long j = p; j < 2 * p; ++j)
        drzewo[j] = max(drzewo[j * 2], drzewo[j * 2 + 1]);

    long skad;
    long va, vb, maxwys;
    bool ok = true;
    for(vector<tSamochod>::iterator it = ustKoncowe.begin(); it != ustKoncowe.end(); ++it) {
      skad = mapaPoczatkowe[it->id];
      if(skad > 0) {
        va = wezlowDrzewa;
        vb = wezlowDrzewa + skad - 1;
        maxwys = drzewo[va];
        if(va != vb)
          maxwys = max(maxwys, drzewo[vb]);
        while(va / 2 != vb / 2) {
          if(va % 2 == 0) maxwys = max(maxwys, drzewo[va + 1]);
          if(vb % 2 == 1) maxwys = max(maxwys, drzewo[vb - 1]);
          va /= 2; vb /= 2;
        }
        if(it->wysokosc + maxwys > w) {
          ok = false;
          break;
        }
      }
      skad += wezlowDrzewa;
      drzewo[skad] = 0;
      while(skad > 1) {
        skad /= 2;
        drzewo[skad] = max(drzewo[2 * skad], drzewo[2 * skad + 1]);
      }
    }
    if(ok)
      cout << "TAK" << endl;
    else
      cout << "NIE" << endl;
  }
  return 0;
}