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

const int N = 50000;

struct SimpleCar {
	int h;
	int id;
	int maxH;
} cars[N], tmp[N];

struct Car {
	int x1; 
	int y1; 
	int x2;
	int y2;
	int id;
} orig[N], dest[N];

int idMapping[N];

bool operator<(Car const& c1, Car const & c2){
	if(c1.x1 == c2.x1)
		return c1.y1 < c2.y1;
	return c1.x1 < c2.x1;
}

void findMaxHs(SimpleCar *from, SimpleCar *until){
	if(from == until) return;
	(until - 1)->maxH = (until - 1)->h;
	if(until - from == 1) return;
	for(SimpleCar *it = until - 2; it >= from; it--)
		it->maxH = std::max(it->h, (it+1)->maxH);
}



bool mergeSort(SimpleCar *from, SimpleCar *until, int w){
	int n = until - from;
	if(n < 2)
		return true;
	
	SimpleCar *mid = from + n/2;
	
	if(!mergeSort(from, mid, w) || !mergeSort(mid, until, w))
		return false;
	findMaxHs(from, mid);
	findMaxHs(mid, until);
	
	SimpleCar *it1 = from;
	SimpleCar *it2 = mid;
	SimpleCar *it3 = tmp;
	while(it1 != mid && it2 != until){
		if(it1->id < it2->id){
			*(it3++) = *(it1++);
		} else {
			if(it2->h + it1->maxH > w) return false;
			*(it3++) = *(it2++);
		}
	}
	while(it1 != mid)
		*(it3++) = *(it1++);
	while(it2 != until)
		*(it3++) = *(it2++);
	std::copy(tmp, tmp + n, from);
	return true;
	
}

void fix(Car & c){
	if(c.x1 > c.x2)
		std::swap(c.x1, c.x2);
	if(c.y1 > c.y2)
		std::swap(c.y1, c.y2);
}

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		int n;
		int w;
		scanf("%d%d", &n, &w);
		for(int i = 0; i < n; i++){
			scanf("%d%d%d%d", &orig[i].x1, &orig[i].y1, &orig[i].x2, &orig[i].y2);
			orig[i].id = i;
			fix(orig[i]);
		}
		for(int i = 0; i < n; i++){
			scanf("%d%d%d%d", &dest[i].x1, &dest[i].y1, &dest[i].x2, &dest[i].y2);
			dest[i].id = i;
			fix(dest[i]);
		}
		std::sort(orig, orig + n);
		std::sort(dest, dest + n);
		for(int i = 0; i < n; i++)
			idMapping[dest[i].id] = i;
		for(int i = 0; i < n; i++){
			cars[i].h = orig[i].y2 - orig[i].y1;
			cars[i].id = idMapping[orig[i].id];
		}
		printf(mergeSort(cars, cars + n, w) ? "TAK\n" : "NIE\n");
	}
	return 0;
}