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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

struct block {
  int x1_, x2_;
  int h_;

  block(int x1, int x2, int h, int idx) : x1_(x1), x2_(x2), h_(h) {}

  bool operator< (const block& bl) {
    return h_ < bl.h_;
  }
};

struct line {
  int x_, h_, idx_;
  bool open_;

  line(int x, int h, int idx, bool open) : x_(x), h_(h), idx_(idx), open_(open) {}

  bool operator< (const line& ln) const {
    if (x_ == ln.x_) {
      if (open_ == ln.open_) {
        return idx_ < ln.idx_;
      }
      return open_ < ln.open_;
    }
    return x_ < ln.x_;
  }
};

vector<block> blocks;
vector<int> big_blocks[2];
set<int> left[2][50000 + 2];

struct block_cmp {
  bool operator() (int x, int y) {
    if (blocks[x].h_ == blocks[y].h_) {
      if (blocks[x].x1_ == blocks[y].x1_) {
        if (blocks[x].x2_ == blocks[y].x2_) {
          return x < y;
        }
        return blocks[x].x2_ < blocks[y].x2_;
      }
      return blocks[x].x1_ < blocks[y].x1_;
    }
    return blocks[x].h_ > blocks[y].h_;
  }
};

void process_boxes(int n, int w, int round) { 
  vector<line> broom;

  blocks.clear();
  big_blocks[round].clear();
  for (int i = 0; i < n; i++) {
    left[round][i].clear();
  }

  for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

    if (x1 > x2) {
      swap(x1, x2);
    }
    if (y1 > y2) {
      swap(y1, y2);
    }

    broom.push_back(line(x1, y2 - y1, i, true));
    broom.push_back(line(x2, y2 - y1, i, false));

    blocks.push_back(block(x1, x2, y2 - y1, i));
  }

  sort(broom.begin(), broom.end(), std::less<line>());
  
  set<int, block_cmp> pending;
  for (int i = 0; i < broom.size(); i++) {
    if (broom[i].h_ > w / 2) {
      if (broom[i].open_) {
        while (!pending.empty() && blocks[*pending.begin()].h_ + broom[i].h_ > w) {
          left[round][broom[i].idx_].insert(*pending.begin());
          pending.erase(pending.begin());
        }
      } else {
        big_blocks[round].push_back(broom[i].idx_);
      }
    } else {
      if (!broom[i].open_) {
        pending.insert(broom[i].idx_);
      }
    }
  }
}

int main() {
  int t;
  scanf("%d", &t);

  while (t--) {
    int n, w;
    scanf("%d%d", &n, &w);

    process_boxes(n, w, 0);
    process_boxes(n, w, 1);

    bool equal = true;

    if (big_blocks[0] != big_blocks[1]) {
      equal = false;
    } else {
      for (int i = 0; i < big_blocks[0].size(); i++) {
        if (left[0][big_blocks[0][i]] != left[1][big_blocks[0][i]]) {
          equal = false;
          break;
        }
      }
    }

    printf("%s\n", equal ? "TAK" : "NIE");
  }

  return 0;
}