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

#define PR std::pair
#define MP std::make_pair
#define X1 first.first.first
#define Y1 first.first.second
#define X2 first.second.first
#define Y2 first.second.second
#define I second
#define TREE_SIZE 131072

int min(int a, int b) {
	if(a < b)
		return a;
	return b;
}

int max(int a, int b) {
	if(a > b)
		return a;
	return b;
}

void build_tree(std::vector<int>* carstree) {
	for(int i = 65535; i > 0; i--)
		(*carstree)[i] = max((*carstree)[2*i], (*carstree)[2*i+1]);
}

int query(int a, int b, std::vector<int>* carstree) {
	a += 65536;
	b += 65536;
	int w = max((*carstree)[a], (*carstree)[b]);
	while(a/2 != b/2) {
		if(a%2 == 0)
			w = max(w, (*carstree)[a+1]);
		if(b%2 == 1)
			w = max(w, (*carstree)[b-1]);
		a /= 2;
		b /= 2;
	}
	return w;
}

void insert(int a, int x, std::vector<int>* carstree) {
	a += 65536;
	(*carstree)[a] = x;
	a /= 2;
	while(a != 0) {
		(*carstree)[a] = max((*carstree)[2*a], (*carstree)[2*a+1]);
		a /= 2;
	}
}

int main() {
	int t;
	scanf("%d", &t);
	for(int h = 0; h < t; h++) {
		int n, w;
		scanf("%d%d", &n, &w);
		std::vector<PR<PR<PR<int,int>,PR<int,int> >,int> > cars, newcars;
		for(int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			cars.push_back(MP(MP(MP(min(x1,x2),min(y1,y2)),MP(max(x1,x2),max(y1,y2))),i));
		}
		for(int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			newcars.push_back(MP(MP(MP(min(x1,x2),min(y1,y2)),MP(max(x1,x2),max(y1,y2))),i));
		}
		std::sort(cars.begin(), cars.end());
		std::vector<PR<int,int> > indexes(n); /* samochod i jest na pozycji;
			indexes[i].first w tablicy cars 
			indexes[i].second w tablicy newcars */
		for(int i = 0; i < n; i++) {
			indexes[cars[i].I].first = i;
			indexes[newcars[i].I].second = i;
		}
		std::sort(newcars.begin(), newcars.end());
		std::vector<int> carstree(TREE_SIZE);//, newcarstree(TREE_SIZE);
		for(int i = 0; i < n; i++)
			carstree[i+65536] = cars[i].Y2 - cars[i].Y1;
		build_tree(&carstree);
		//for(int i = 0; i < n; i++)
			//newcarstree[i+65536] = newcars[i].Y1 - newcars[i].Y2;
		bool b = true;
		for(int i = n-1; i >= 0; i--) {
			// indexes[newcars[i].I].first - pozycja aktualnego samochodu w tablicy cars
			int q = query(indexes[newcars[i].I].first+1, n-1, &carstree);
			if(q > w-(newcars[i].Y2-newcars[i].Y1)) {
				printf("NIE\n");
				b = false;
				break;
			}
			insert(indexes[newcars[i].I].first, 0, &carstree);
		}
		if(b)
			printf("TAK\n");
	}
	return 0;
}