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
#include<cstdio>
#include<algorithm>
using namespace std;

struct sam
{
int h,p,nr;
};

sam twe[50009],twy[50009];
int td[132000],pot;


int min(int a, int b)
{
if(a<b) return a; else return b;
}

int max(int a, int b)
{
if(a>b) return a; else return b;
}

int abs(int a)
{
if(a<0) return a*-1; else return a;
}

bool pcomp(sam a, sam b)
{
if(a.p<b.p) return true; else return false;
}

bool nrcomp(sam a, sam b)
{
if(a.nr<b.nr) return true; else return false;
}

void update(int nr, int x)
{
nr+=pot;
td[nr]=x;
while(nr>1)
{
	if(nr%2==1) nr--;
	td[nr/2]=max(td[nr],td[nr+1]);
	nr/=2;
}
}

int zwroc(int p, int k)
{
int wyn;
if(k<0) return 0;
p+=pot;
k+=pot;
wyn=max(td[p],td[k]);
while(p!=k)
{
	wyn=max(td[p],td[k]);
	p/=2;
	k/=2;
}
return wyn;
}

int main()
{
int t,n,h,x1,y1,x2,y2;
bool wyn;
scanf("%d",&t);
for (int k=0;k<t;k++)
{
	scanf("%d%d",&n,&h);
	pot=1;
	wyn=true;
	while(pot<n) pot*=2;
	for (int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		twe[i].p=min(x1,x2);	
		twe[i].h=abs(y1-y2);
		twe[i].nr=i;
	}
	sort(twe,twe+n,pcomp);
	for (int i=0;i<n;i++)
	{
		twe[i].p=i;
		update(i,twe[i].h);
				//printf("%d ",twe[i].h);
	}
				//printf("\n");
	sort(twe,twe+n,nrcomp);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		twy[i].p=min(x1,x2);	
		twy[i].h=abs(y1-y2);
		twy[i].nr=twe[i].p;
	}
	sort(twy,twy+n,pcomp);
	for(int i=0;i<n;i++)
	{
		
//printf("%d %d %d %d\n",twy[i].nr,twy[i].h,zwroc(0,twy[i].nr-1),h);		
		
		if(h-zwroc(0,twy[i].nr-1)<twy[i].h)
		{
			wyn=false;
			break;
		}
		update(twy[i].nr,0);
	}
	if(wyn) printf("TAK\n"); else printf("NIE\n");
	for (int i=0;i<n;i++) update(i,0);
}
return 0;
}