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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct obj {
	int x;
	int h;
	int n;	
};

inline obj make_obj(int a, int b, int c) {
	obj ret;
	ret.x = a;
	ret.h = b;
	ret.n = c;
	return ret;	
}

struct comp__ {
  bool operator() (obj i, obj j) { return (i.x<j.x); }
} comp;

int M;
int* tree;
bool tc;

void insert_tree(int x, int val) { 

   int v = M + x;
   tree[v-1] = val;
   while (v != 1) {
     	v /= 2;
     	tree[v-1] = max(tree[2 * v -1], tree[2 * v]);
   }
}


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

int main(void) {
	ios_base::sync_with_stdio(0);
	int t=0, n, w, x1, y1, x2, y2;
	bool good = true;
	vector< obj > v1, v2;
	
	cin>>t;
	for(int j=0;j<t;++j) {
		cin>>n>>w;	
		v1.clear();
		v2.clear();
		for(int it=0;it<n;++it) {
			cin>>x1>>y1>>x2>>y2;
			v1.push_back(make_obj(x1, y2-y1, it));
		}
		for(int it=0;it<n;++it) {
			cin>>x1>>y1>>x2>>y2;
			v2.push_back(make_obj(x1, y2-y1, it));
		}
		sort(v1.begin(), v1.end(), comp);
		sort(v2.begin(), v2.end(), comp);
		
		if(n%2==0) {
			M = n;	
			tc = false;
		} else {
			M = n+1;
			tc = true;
		}
		tree = new int[2*M-1];
		for(int it=0;it<2*M-1;++it) {
			tree[it] = -1;
		}
		for(int it=0;it<n;++it) {
			insert_tree(it, v1[it].h);	
		}
		good = true;
		for(int it=0;it<n;++it) {
			for(int k=0;k<n;++k) {
				if(v1[it].n==v2[k].n && it!=k) {
					int f, t;
					if(it<k) {
						f=it;
						t=k;	
					} else {
						f=k;
						t=it;	
					}
					
					if(v1[f].h+query(f+1, t) > w) {
						good=false;
						k=n;
						it=n;
					}
				}
			}	
		}
		if(good) {
			cout<<"TAK\n";
		} else {
			cout<<"NIE\n";	
		}
		
		
		
	}
	
	return 0;
}