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
119
120
#include<cstdio>
#include<algorithm>
#include<vector>
#define ft first
#define sd second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppp;
const int shift= (1<<16),maxn=5e4+7;
int tab[shift<<1],przed[maxn],po_order[maxn],po[maxn],h_order[maxn],h_id[maxn];
ppp coords1[maxn],coords2[maxn];
int n,t,w;

inline int h(int i)
{
	return abs(coords1[i].sd.sd-coords1[i].ft.sd);
}
bool wysokosci(int a,int b)
{
	if(h(a)<h(b))return true;
	return false;
}
bool comp1(int a,int b)
{
	if(coords1[a].ft.ft<coords1[b].ft.ft)return true;
	return false;
}
bool comp2(int a,int b)
{
	if(coords2[a].ft.ft<coords2[b].ft.ft)return true;
	return false;
}
int get_max(int a)
{
	a+=shift;
	int aa=a;
	int out=tab[a];
	a>>=1;
	while(a>0)
	{
		if(!(aa&1))out=max(out,tab[aa+1]);
		aa=a;
		a>>=1;
	}
	return out;
}
void add(int a,int val)
{
	a+=shift;
	tab[a]=val;
	a>>=1;
	while(a>0)
	{
		tab[a]=max(tab[a<<1],tab[(a<<1)+1]);
		a>>=1;
	}
}
int znajdz_pierwszy(int val)
{
	int a=1,b=n,s;
	while(a<b)
	{
		s=((a+b)>>1);
		if(h(h_order[s])>val)b=s;
		else a=s+1;
	}
	if(a==n && h(h_order[a])<=val)a++;
	return a;
}
bool solve()
{
	sort(przed+1,przed+n+1,comp1);
	sort(po_order+1,po_order+n+1,comp2);
	sort(h_order+1,h_order+n+1,wysokosci);
	/*fprintf(stderr,"PRZED: \n");
	for(int i=1;i<=n;i++)fprintf(stderr,"%d ",przed[i]);
	fprintf(stderr,"\n");
	fprintf(stderr,"PO: \n");
	for(int i=1;i<=n;i++)fprintf(stderr,"%d ",po_order[i]);
	fprintf(stderr,"\n");*/
	for(int i=1;i<=n;i++)
	{
		h_id[h_order[i]]=i;
		po[po_order[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int a=znajdz_pierwszy(w-h(przed[i]));
		//fprintf(stderr,"%d\n",a);
		int b=get_max(a);
		//fprintf(stderr,"b=%d\n",b);
		if(b>po[przed[i]])return false;
		add(h_id[przed[i]],po[przed[i]]);
	}
	return true;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&w);
		for(int i=1;i<(shift<<1);i++)tab[i]=0;
		for(int i=1;i<=n;i++)
		{
			przed[i]=po_order[i]=h_order[i]=i;
			scanf("%d%d%d%d",&coords1[i].ft.ft,&coords1[i].ft.sd,&coords1[i].sd.ft,&coords1[i].sd.sd);	
			if(coords1[i].ft.ft>coords1[i].sd.ft)swap(coords1[i].ft,coords1[i].sd);
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d%d",&coords2[i].ft.ft,&coords2[i].ft.sd,&coords2[i].sd.ft,&coords2[i].sd.sd);	
			if(coords2[i].ft.ft>coords2[i].sd.ft)swap(coords2[i].ft,coords2[i].sd);
		}
		if(solve())printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}