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

struct car_t {
	int x1, x2, w, i;
};

bool compByX1(const car_t& a, const car_t& b) { return a.x1 < b.x1; }
bool compByX2(const car_t& a, const car_t& b) { return a.x2 < b.x2; }

inline int abs(const int a) { return a >= 0 ? a : -a; }
inline int min(const int a, const int b) { return a < b ? a : b; }

car_t cars[50000];

void test() {
	int n, w;
	scanf("%d %d", &n, &w );
	for( int i = 0; i < n; i++ ) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d );
		cars[i].x1 = min(a,c);
		cars[i].w = abs(b-d);
	}
	for( int i = 0; i < n; i++ ) {
		int a, c;
		scanf("%d %*s %d %*s", &a, &c );
		cars[i].x2 = min(a,c);
	}
		

	std::sort(cars, cars+n, compByX1);
	for( int i = 0; i < n; i++ )
		cars[i].i = i;

	std::sort(cars, cars+n, compByX2);
	std::map<int, int> Cross;
	Cross[n] = 0;

	for( int i = 0; i < n; i++ ) {
		//fprintf(stderr, "NEW CAR: wysokosc=%d\n", cars[i].w );
		//for(  = Cross.begin(); it != Cross.end(); it++ )
		//	fprintf(stderr, "(%d,%d) ", it->first, it->second );
		//fprintf(stderr,"\n");
		int cross = Cross.lower_bound(cars[i].i)->second;
		if( cars[i].w+cross > w ) {
			puts("NIE");
			//fprintf(stderr, "%d collided with %d\n", cars[i].i, Cross.lower_bound(cars[i].i)->first);
			return;
		}
		if( cars[i].w > cross ) {
			Cross[cars[i].i] = cars[i].w;
			std::map<int, int>::iterator it = Cross.find(cars[i].i);
			--it;
			while( it != Cross.end() and it->second < cars[i].w ) {
				std::map<int, int>::iterator rit = it;
				--it;
				Cross.erase(rit); 
			}
		}
	}

	puts("TAK");
}

int main() {
	int T;
	scanf("%d", &T );
	while( T --> 0 )
		test();
}