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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

struct Car
{
  size_t x1, x2, y1, y2;
  size_t *id;
  size_t width() const { return x2 - x1; }
  size_t height() const { return y2 - y1; }
};

template<typename Stream>
Stream& operator>>(Stream &is, Car &car)
{
  is >> car.x1 >> car.y1 >> car.x2 >> car.y2;
  return is;
}

template<typename Stream>
Stream& operator<<(Stream &os, Car const &car)
{
  os << "{ [" << car.x1 << ", " << car.y1 << ", " << car.x2 << ", " << car.y2 << "]"
     << "h = " << car.height() << ", w = " << car.width() << ", id = " << *car.id << " }";

  return os;
}

struct XthenHeight
{
  bool operator()(Car const &l, Car const &r) const
  {
    if(l.x1 != r.x1)
      return l.x1 < r.x1;
    return l.height() < r.height();
  }
};

template<typename Container>
void print(Container const &c)
{
  for(typename Container::const_iterator it = c.begin(); it != c.end(); ++it)
    cout << *it << endl;
}

typedef vector<Car> Cars;

int main()
{
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);

  size_t t;
  cin >> t;

  while(t --> 0)
  {
    size_t n, w;
    cin >> n >> w;

    Cars before;
    Cars after;
    typedef vector<size_t> ID;
    ID ids;
    ids.resize(n);
    before.resize(n);
    after.resize(n);

    for(size_t i = 0; i < n; ++i)
    {
      ids[i] = i;
      cin >> before[i];
      before[i].id = &ids[i];
    }
    for(size_t i = 0; i < n; ++i)
    {
      cin >> after[i];
      after[i].id = &ids[i];
    }

    sort(before.begin(), before.end(), XthenHeight());
    sort(after.begin(), after.end(), XthenHeight());
    // do we have a collision?
    typedef map<size_t, size_t> Map;
    Map idsMap;
    for(size_t i = 0; i < n; ++i)
      for(size_t j = i + 1; j < n; ++j)
        if(*after[j].id < *after[i].id)
          idsMap[*after[j].id] = *after[i].id;

    bool possiible = true;
    for(Map::const_iterator it = idsMap.begin(); it != idsMap.end(); ++it)
    {
      bool ok = true;
      for(size_t i = it->first; i < it->second; ++i)
      {
        if(before[it->second].height() > (w - before[i].height()))
        {
          ok = false;
          break;
        }
      }
      if(!ok)
      {
        possiible = false;
        break;
      }
    }

    cout << (possiible ? "TAK" : "NIE") << endl;
  }


  return 0;
}