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
#include <cstdio>
#include <algorithm>
#include <vector>
#define scanf(args...) scanf(args) ? : 0
#define MP make_pair
#define X1 first.first.first
#define H first.first.first
#define Y1 first.first.second
#define X2 first.second.first
#define Y2 first.second.second
#define N second
#define all(q) (q).begin(),(q).end()
using namespace std;
typedef pair<pair<pair<int,int>,pair<int,int>>,int> T;
const int MAX=5e4+12;
int n,h;
vector<T> cars1, cars2;
int q[MAX],d[MAX];
int tree[8*MAX];
int x;
void build()
{
	x=1;
	while(x<n)
		x*=2;
	for(int i=1;i<=2*x;i++)
		tree[i]=0;
}
void insert(int index, int p)
{
	index+=x;
	//printf("INSERT: %d %d\n",index,p);
	tree[index]=max(tree[index],p);
	while(index!=1)
	{
		index/=2;
		tree[index]=max(tree[index*2],tree[index*2+1]);
	}
}
int query(int a, int b)
{
	if(b<a)return 0;
	//printf("QUERY: %d %d\n",a,b);
	a+=x;b+=x;
	int res=max(tree[a],tree[b]);
	while(a/2!=b/2)
	{
		if(a%2==0)res=max(res,tree[a+1]);
		if(b%2==1)res=max(res,tree[b-1]);
		a/=2;
		b/=2;
	}
	return res;
}
void input(vector<T> &c)
{
	c.resize(n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&c[i].X1,&c[i].Y1,&c[i].X2,&c[i].Y2);
		c[i].N=i;
	}
}
bool check()
{
	for(int i=0;i<n;i++)
	{
		//printf("%d %d %d %d\n",i,d[i],query(i+1,d[i]),cars2[d[i]].H);
		if(query(i+1,d[i])+cars2[d[i]].H>h)
			return false;
		else
			insert(d[i]+1,0);
	}
	return true;
}
void solve()
{
	scanf("%d%d",&n,&h);
	build();
	input(cars1);
	input(cars2);
	sort(all(cars1));
	sort(all(cars2));
	//for(int i=0;i<n;i++)
	//	printf("%d %d %d %d\n",cars2[i].X1,cars2[i].Y1,cars2[i].X2,cars2[i].Y2);
	for(int i=0;i<n;i++)
		q[cars1[i].N]=i;
	for(int i=0;i<n;i++)
		cars2[i].N=q[cars2[i].N];
	//for(int i=0;i<n;i++)
	//	printf("%d ",cars2[i].N);
	for(int i=0;i<n;i++)
		d[cars2[i].N]=i;
	for(int i=0;i<n;i++)d[i]=cars2[i].N;
	//printf("\n");
	//for(int i=0;i<n;i++)
	//	printf("%d ",d[i]);
	//printf("\n");
	for(int i=0;i<n;i++)
	{
		cars2[i].H=abs(cars2[i].Y1-cars2[i].Y2);
		insert(i+1,cars2[i].H);
	}
	//for(int i=0;i<2*x;i++)
	//	printf("%d ",tree[i]);
	printf("%s\n",check()?"TAK":"NIE");
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
		solve();
}