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
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <algorithm>
#include <map>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define TR(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)

vi bounds(vvi& p, int w)
{
  map<int, int>::iterator it;
  map<int, int> bds;
  vi res(p.size());
  bds[w+1] = -1;

  TR(iv,p){
    int wi = abs((*iv)[3] - (*iv)[1]);
    it = bds.lower_bound(w-wi+1);
    res[(*iv)[4]] = (it->second);

    if (wi > w/2){
      it = bds.lower_bound(wi);
      bds.erase (bds.begin(), it);
      bds[wi] = (*iv)[4];
    }
  }
  return res;
}

void solve(){
  int w,n;
  vvi p1;
  vvi p2;
  vi v1, v2;
  vi c(5);

  scanf("%d %d", &n, &w);

  FOR(j,0,n) {
    scanf("%d %d %d %d", &c[0], &c[1], &c[2], &c[3]);
    c[4] = j;
    p1.push_back(c);
  }
  FOR(j,0,n) {
    scanf("%d %d %d %d", &c[0], &c[1], &c[2], &c[3]);
    c[4] = j;
    p2.push_back(c);
  }

  sort(p1.begin(),p1.end());
  sort(p2.begin(),p2.end());

  v1 = bounds(p1,w);
  v2 = bounds(p2,w);

  FOR(j,0,n)
    if (v1[j] != v2[j]){
      printf("NIE\n");
      return;
    }

  printf("TAK\n");
    
}

int main() 
{
  int t;
  scanf("%d", &t);
  FOR(i,0,t) solve();
  return 0;
}