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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 50000

using namespace std;

struct klocek {
	int x1, y1, x2, y2;
	int nr, height;
	klocek () {
		x1 = y1 = x2 = y2 = nr = height = 0;
	};
	klocek(int _x1, int _y1, int _x2, int _y2, int _nr) {
		x1 = _x1;
		y1 = _y1;
		x2 = _x2;
		y2 = _y2;
		nr = _nr;
		height = abs(y2-y1);
	}
	
	void print()
	{
		printf("klocek nr %d: %d %d %d %d\n", nr+1, x1, y1, x2, y2);
	}
};

bool operator< (const klocek &A, const klocek &B) {
	if(A.x1 == B.x1)
	{
		if(A.x2 == B.x2)
			return A.nr < B.nr;
		return A.x2 < B.x2;
	}
	return A.x1 < B.x1; // mniejszy ten, ktory jest wczesniej
}

int n, w;
int M = 1;
klocek arr[MAXN+7], arr2[MAXN+7];
int nowaKol[MAXN+7]; //pod jakim nowym nr znajde stare i

int tree[1000000]; //DUZE DRZEWO

void read()
{
	scanf("%d %d", &n, &w);
	while(M < n)
		M *= 2;
	int x1, y1, x2, y2;
	for(int i=0; i<n; i++)
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		arr[i] = klocek(x1, y1, x2, y2, i);
	}
	for(int i=0; i<n; i++)
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		arr2[i] = klocek(x1, y1, x2, y2, i);
	}
}

void addToTree(int wys, int i)
{
	int v = M + i;
	tree[v] = wys;
	while(v != 1)
	{
		v /= 2;
		tree[v] = max(tree[2*v], tree[2*v+1]);
	}
}

int query(int a, int b)
{
	if(a == 0 && b == 0)
		return 0;
	int l = a+M, r = b+M; 
	int wyn = tree[l];
	while(l/2 != r/2)
	{
		if(l % 2 == 0)
			wyn = max(wyn, tree[l+1]);
		if(r % 2 == 1)
			wyn = max(wyn, tree[r-1]);
		l /= 2; r /= 2;
	}
	return wyn;
	
}

void makeTree()
{
	for(int i=0; i<n; i++)
		addToTree(arr[i].height, i);
}

bool solve()
{
	sort(arr, arr+n);
	sort(arr2, arr2+n);
	for(int i=0; i<n; i++)
	{
		int tmp = arr[i].nr;
		nowaKol[tmp] = i;
	}
	makeTree(); //ROB DRZEWO, WSTAW KAZDY ELEMENT
	for(int i=0; i<n; i++)
	{
		int wys = query(0, nowaKol[arr2[i].nr]);
		//printf("%d %d ", wys, nowaKol[arr2[i].nr]);
		if(w-wys < arr2[i].height)
			return 0;
		else
			addToTree(0, nowaKol[arr2[i].nr]);
	}
}

void clean()
{	
	for(int i=0; i<1000000; i++)
		tree[i] = 0;
	M = 1;
}

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