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
#include <stdio.h>

typedef struct Sam 
{
 int x1,y1,x2,y2;
 int h;
 int i;
 struct Sam *d;
 int di;
 int ok;
} Sam;

Sam org[50000],doc[50000];

int cmpSx (const void *a,const void *b)
{
   int p=((*(Sam*)a).x1-(*(Sam*)b).x1);
   if(p)return p;
   return ((*(Sam*)a).h-(*(Sam*)b).h);
}
 
int main(void)
{
 int t,i=0,j;
 int n,w;
 int x1,y1,x2,y2,pp;
 int ans;
 scanf("%d",&t);
 for(;i<t;++i)
 {
  ans=1;
  scanf("%d %d",&n,&w);
  for(j=0;j<n;++j)
  {
   scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
   if(x1>x2)
   {
    pp=x1;x1=x2;x2=pp;
    pp=y1;y1=y2;y2=pp;
   }
   if(y1>y2)
   {
    pp=y1;y1=y2;y2=pp;
   }
   org[j].x1=x1;org[j].x2=x2;org[j].y1=y1;org[j].y2=y2;
   org[j].h=y2-y1;
   org[j].i=j;
   org[j].ok=1;
  }
  for(j=0;j<n;++j)
  {
   scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
   if(x1>x2)
   {
    pp=x1;x1=x2;x2=pp;
    pp=y1;y1=y2;y2=pp;
   }
   if(y1>y2)
   {
    pp=y1;y1=y2;y2=pp;
   }
   doc[j].x1=x1;doc[j].x2=x2;doc[j].y1=y1;doc[j].y2=y2;
   doc[j].h=y2-y1;
   doc[j].i=j;
  }
  qsort(org, n, sizeof(Sam), cmpSx);
  for(j=0;j<n;++j){
   doc[org[j].i].d=org+j;
   doc[org[j].i].di=j;
  }
  qsort(doc, n, sizeof(Sam), cmpSx);
  for(j=0;j<n;++j){
   (*(doc[j].d)).d=org+j;
   (*(doc[j].d)).di=j;
  }
  int k,po,oh;
  for(j=0;j<n && ans;++j){
   po=doc[j].di;
   oh=org[po].h;
   for(k=po-1;k>=0;--k){
    if(org[k].ok && oh+org[k].h>w){
     ans=0;
     break;
    }
   }
   org[po].ok=0;
  }
  printf(ans?"TAK\n":"NIE\n");
 }
 return 0;
}