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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>

#define fru(j,n) for(int j=0;j<n;++j)
#define tr(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

const int MAXN= 100005;

pii P[2][MAXN];
int H[MAXN];
int kto;
bool cmp(const int &a, const int &b)
{
	return P[kto][a]<P[kto][b];
}
int TAB[2][MAXN];

int D[MAXN],INV[MAXN];
int n;
inline int mag(int x) {return x-(x&(x-1));}
int licz(int u)
{
	int ret=0;
	while(u)
	{
		ret=max(ret,D[u]);
		u-=mag(u);
	}
	return ret;
}
void add(int u, int x)
{
	while(u<=n)
	{
		D[u]=max(D[u],x);
		u+=mag(u);
	}
}

bool solve()
{
	int wys;
	scanf("%d%d",&n,&wys);
	fru(o,2) fru(i,n)
	{
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		P[o][i]=pii(min(x1,x2),min(y1,y2));
		if(o) assert(H[i]==abs(y1-y2));
		H[i]=abs(y1-y2);
	}
	fru(i,2) fru(j,n) TAB[i][j]=j;
	fru(i,MAXN) D[i]=0;
	fru(k,2)
	{
		kto=k;
		sort(TAB[k],TAB[k]+n,cmp);
//		printf("ord(%d):\n",k);		fru(i,n) printf("%d ",TAB[k][i]); printf("\n");
	}

	fru(i,n) INV[TAB[0][i]]=i+1;
	for(int i=n-1;i>=0;--i)
	{
		int u=TAB[1][i];
		if(licz(INV[u])+H[u]>wys) return 0;
		add(INV[u],H[u]);
	}
	return 1;
}

int main()
{
	int te;
	scanf("%d",&te);
	while(te--) printf("%s\n",solve()?"TAK":"NIE");
	return 0;
}