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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;

int x1[20005];
int x2[20005];
int y2[20005];
int x21[20005];
int x22[20005];
int y21[20005];
int y22[20005];
int wysokosc[20005];
int szerokosc[20005];
int odw[20005];
int coscos[20005];
vector<PII>v,v2;

int main(){
  ios_base::sync_with_stdio(0);
  int t;
  cin >> t;
  for(int k=0; k<t; k++){
    int n,w;
    cin >> n >> w;
    for(int i=0; i<n; i++){
      int a,b,c,d;
      cin >> x1[i] >> coscos[i] >> x2[i] >> y2[i];
    }
    for(int i=0; i<n; i++){
      if(x1[i]<x2[i]) szerokosc[i]=x1[i]-x2[i];
      else szerokosc[i]=x2[i]-x1[i];
      if(coscos[i]>=y2[i]) wysokosc[i]=coscos[i]-y2[i];
      else wysokosc[i]=y2[i]-coscos[i];
    }
    for(int i=0; i<n; i++){
      if(x1[i]>=x2[i]) v.push_back(PII(x1[i], i));
      else v.push_back(PII(x2[i],i));
    }
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++){
      cin >> x21[i] >> y21[i] >> x22[i] >> y22[i];
    }
    for(int i=0; i<n; i++){
      if(x21[i] < x22[i]) v2.push_back(PII(x21[i],i));
      else v.push_back(PII(x22[i],i));
    }
    sort(v.begin(),v.end());
    sort(v2.begin(),v2.end());
    bool prawda=false;
    for(int i=0; i<n; i++){
      int a=v2[i].second;
      odw[v2[i].second]=1;
      for(int j=i-1; j>=0; j--){
        if(odw[v[j].second]==1) continue;
        if(wysokosc[v2[i].second]+wysokosc[v[j].second]<w) continue;
        else{
          prawda=true;
          break;
        }
      }
      if(prawda==true) continue;
      for(int j=i-1; j>=0; j--){
      int b=min(x21[v2[i].second], x22[v2[i].second]);
      int c=max(x22[v2[j].second], x22[v2[j].second]);
      if(b>=c) continue;
      int d=max(y21[v2[i].second], y22[v2[i].second]);
      int e=max(y21[v2[j].second], y22[v2[j].second]);
      int f=min(y21[v2[i].second], y22[v2[i].second]);
      int g=min(y21[v2[j].second], y22[v2[j].second]);
      if(d>=e){
        if(w-e<wysokosc[v2[i].second]) {
        prawda=true;
        break;
        }
      }
      else{
        if(f<=g){
          if(g<wysokosc[v2[i].second]){
            prawda=true;
            break;
          }
        }
      }
      if(wysokosc[v2[i].second]+wysokosc[v2[j].second]<=w) continue;
      else prawda=true;
      }
    }
  if(prawda==false) cout << "TAK" << endl;
  else cout << "NIE" << endl;
  }
  return 0;
}