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
#include <stdio.h>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

class O
{
public:
  int x1[2],x2[2],y1[2],y2[2],p[2];
  void wypisz()
  {
    printf("%d %d %d %d p1:%d p2:%d\n",x1[0],y1[0],x2[0],y2[0],p[0],p[1]);
    printf("%d %d %d %d\n",x1[1],y1[1],x2[1],y2[1]);
  }
};

O tab[50100];


int main()
{
  int t;
  scanf("%d",&t);
  for(;t--;)
  {
    set<pair<int,int> > s[2];
    int n,w,x1,x2,y1,y2;
    scanf("%d%d",&n,&w);
    for(int j=0;j<2;j++)
    for(int i=0;i<n;i++)
    {
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      tab[i].x1[j] = min(x1,x2);
      tab[i].y1[j] = min(y1,y2);
      tab[i].x2[j] = max(x1,x2);
      tab[i].y2[j] = max(y1,y2);
      s[j].insert(make_pair(tab[i].x1[j],i)); 
    }
    for(int j=0;j<2;j++)
    {
      int i=0;
      for(set<pair<int,int> >::iterator it=s[j].begin();it!=s[j].end();++it,i++)
      {
        tab[it->second].p[j]=i;
      }
    }
    
    set<pair<int,int> >g;
    for(int i=0;i<n;i++)
    {
      g.insert(make_pair(tab[i].y2[0]-tab[i].y1[0],i));
    }
    
    
    bool failed=false;
    
    set<pair<int,int>>::reverse_iterator it=g.rbegin();

    while(it!=g.rend() && it->first+(g.rbegin()->first)>w && !failed) 
    {
      if (tab[it->second].p[0] == tab[it->second].p[1]) {++it;continue;}
      set<pair<int,int>>::reverse_iterator it2=g.rbegin();
      while(it2!=g.rend() && it2->first+(it->first)>w && !failed)
      {
        int i=it->second;
        int j=it2->second;
        if(((long long)(tab[i].p[1]-tab[j].p[1]))*((long long)(tab[i].p[0]-tab[j].p[0]))<0)
        {
          failed=true;
      //    printf("%d %d %d %d\n",i,j,it->first,it2->first);
        //  tab[i].wypisz();
          //tab[j].wypisz();
        }
        ++it2;
      }
      ++it;
    }

    if(failed) cout<<"NIE"<<endl;
    else cout << "TAK"<<endl;
  }
  return 0;
}