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

using namespace std;

int t, n, w, x1, y3, x2, y2, siz, pom, h;

bool czy;

int tree[150000];

pair <pair <int, int> , int> car[50000], car2[50000];
int carp[50000];

int maks (int pr, int pq) {
	if (pr > pq)
		return pr;
	return pq;
}
void insert(int a, int b) {
	int va = a + siz;
	
	tree[va] = b;
	
	while (va != 1) {
		va /= 2;
		tree[va] = maks(tree[2*va], tree[2*va+1]);
	}
}

int query(int a) {
	if (a == 0)
		return 0;
	int vb = a + siz - 1;
	int va = siz;
	int wyn = max(tree[vb], tree[va]);
	while (va/2 != vb/2) {
		if (va % 2 == 0) {
			if (tree[va+1] > wyn)
				wyn = tree[va+1];
		}
		if (vb % 2 == 1) {
			if (tree[vb-1] > wyn)
				wyn = tree[vb-1];
		}
		va /= 2;
		vb /= 2;		
	}
	return wyn;
}
int main() {
	
	scanf("%d", &t);
	while (t--) {
		czy = 0;
		siz = 1;
		scanf("%d%d", &n, &w);
		
		while (siz < n)
			siz *= 2;
		
		for (int i = 0; i < n; i++) {
			scanf("%d%d%d%d", &x1, &y3, &x2, &y2);
			car[i] = make_pair( make_pair(x1, y2-y3) , i);
		}
		sort(car, car + n);
		
		for (int i = 0; i < n; i++) {
			insert(i, car[i].first.second);
			carp[car[i].second] = i;
		}
		
	/*	for (int i = 0; i < siz + n; i++)
			printf("%d ", tree[i]);
	printf("\n");
		for (int i = 0; i < n; i++)
			printf("%d ", carp[i]);
		printf("\n"); */	
		for (int i = 0; i < n; i++) {
			scanf("%d%d%d%d", &x1, &y3, &x2, &y2);
			car2[i] = make_pair( make_pair(x1, y2-y3), i);	
		}
		sort(car2, car2 + n);
		
	/*	for (int i = 0; i < n; i++)
			printf("%d ", car2[i].second);
		printf("\n"); */
		
		for (int i = 0; i < n; i++) {
			pom = carp[car2[i].second];
			h = car2[i].first.second;
			if (query(pom) + h > w) {
				printf("NIE \n");
				czy = 1;
				break;
			}
			insert(pom, 0);
		}
		if (czy == 0)
			printf("TAK \n");
		for (int i = 0; i < n + siz; i++)
			tree[i] = 0;
	}
	return 0;
	}