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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

namespace {
  struct car {
    int x0;
    int x1;
    int h;
  };

  template <typename Cmp>
  vector<int> perm(vector<car> const& v, Cmp&& cmp)
  {
    vector<int> p(v.size());
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int a, int b) { return cmp(v[a], v[b]); });
    return p;
  }

  vector<int> get_sig(vector<car> const& v, vector<int> const& p, int h)
  {
    vector<int> res(v.size());

    tree<pair<int, int>, null_mapped_type, greater<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> cur;

    for (auto const& i: p) {
      res[i] = cur.order_of_key({h - v[i].h + 1, -1});
      cur.insert({v[i].h, i});
    }

    return res;
  }

  bool solve(vector<car> const& cars, int h)
  {
    auto p0 = perm(cars, [](car const& a, car const& b) { return a.x0 < b.x0; });
    auto p1 = perm(cars, [](car const& a, car const& b) { return a.x1 < b.x1; });

    auto s0 = get_sig(cars, p0, h);
    auto s1 = get_sig(cars, p1, h);

    return s0 == s1;
  }
}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin >> t;
  while (t > 0) {
    --t;

    int n, w;
    cin >> n >> w;
    vector<car> cars(n);
    for (int i = 0; i < n; ++i) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      cars[i].x0 = min(x1, x2);
      cars[i].h = abs(y1 - y2);
    }
    for (int i = 0; i < n; ++i) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      cars[i].x1 = min(x1, x2);
    }

    cout << (solve(move(cars), w) ? "TAK" : "NIE") << '\n';
  }

  return 0;
}