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

int t, n, w;

int k;

struct q{
	int x1, y1;
	int x2, y2;
	int wys;
	int nr;
	
	void ustaw_nr() {
		nr = k++;
	}
	
	void ustaw_wys() {
		wys = y2 - y1;
	}
} el1, tab[50000], tab2[50000];

bool cmp(const q &el1,const q &el2) {
	return (el1.x1 < el2.x1) || ((el1.x1 == el2.x1) && (el1.y1 < el2.y1)); 
}

int main() {
	scanf("%d",&t);
	while(t--) {
		k = 0;
		scanf("%d%d",&n,&w);
		for(int i = 0; i < n; ++i) {
			scanf("%d%d%d%d",&tab[i].x1, &tab[i].y1, &tab[i].x2, &tab[i].y2);
//			tab[i].ustaw_wys();
			tab[i].nr = i;
		}
		for(int i = 0; i < n; ++i) {
			scanf("%d%d%d%d",&tab2[i].x1, &tab2[i].y1, &tab2[i].x2, &tab2[i].y2);
			tab2[i].ustaw_wys();
		}
		
		sort(tab, tab+n, cmp);
		
		for(int i = 0; i < n; ++i) {
			tab2[tab[i].nr].ustaw_nr();
		}

		sort(tab2, tab2+n, cmp);

		//question: czy da się posortować tab2 względem nr?
		bool end = false;
		for(int i = 1; i < n; ++i) {
			int j = i;
			while(j>0 && tab2[j-1].nr > tab2[j].nr) {
				if(tab2[j].wys + tab2[j-1].wys <= w) swap(tab2[j],tab2[j-1]);
				else {printf("NIE\n"); end = true; break;}
				j--;
			}
			if(end == true) break;
		}
		
		if(end == false) printf("TAK\n"); 
	}
}