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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct _sam{
	int nr1;
	int nr2;
	int w;
}sam;

typedef struct _sam1{
	int nr;
	int x;
}sam1;

int compar1( const void * s1, const void * s2 ){
	if ( ((sam1*)s1)->x > ((sam1*)s2)->x ) return 1;
	if ( ((sam1*)s1)->x < ((sam1*)s2)->x ) return -1;
	return 0;
}

int compar2( const void * s1, const void * s2 ){
	if ( ((sam*)s1)->w < ((sam*)s2)->w ) return 1;
	if ( ((sam*)s1)->w > ((sam*)s2)->w ) return -1;
	return 0;
}

int main(int argc, char *argv[]){
	int t;		// liczba testow
	int n;  	// liczba samochodow
	int w; 	// wysokosc parkingu
	int ws;	// wysokosc samochodu
	int x1,x2,y1,y2;
	sam1 * s1;
	sam1 * sa;
	sam * s2;
	sam * s;
	int k,l;
	int tak;
	

	scanf( "%d", &t );
	while (t--){
		scanf( "%d %d", &n, &w );

		s1 = (sam1 *)malloc( n*sizeof(sam1) );
		s2 = (sam *)malloc( n*sizeof(sam) );
		
		for (k=0,sa=s1; k<n; k++,sa+=1){
			sa->nr = k;
			scanf( "%d %d %d %d", &x1, &y1, &x2, &y2);
			if (x1 < x2){
				sa->x = x1;
			} else {
				sa->x = x2;
			}
		}
		qsort( s1, n, sizeof(sam1), compar1 );
		for (k=0,sa=s1; k<n; k++,sa+=1){
			s2[sa->nr].nr1 = k;
		}
		for (k=0,sa=s1,s=s2; k<n; k++,sa+=1,s+=1){
			scanf( "%d %d %d %d", &x1, &y1, &x2, &y2);
			sa->nr = k;
			if (x1 < x2){
				sa->x = x1;
				//s->s = x2 - x1;
			} else {
				sa->x = x2;
				//s->s = x1 - x2;
			}
			if (y1 < y2){
				s->w = y2 - y1;
			} else {
				s->w = y1 - y2;
			}			
		}
		qsort( s1, n, sizeof(sam1), compar1 );
		for (k=0,sa=s1; k<n; k++,sa+=1){
			s2[sa->nr].nr2 = k;
		}
		qsort( s2, n, sizeof(sam), compar2 );
		tak = 1;
		for (k=0; k<n; k++){
			ws = s2[k].w; 
			if (ws+ws <= w)
				break;
			for (l=k; l<n; l++){
				if (ws+s2[l].w <= w)
					break;
				x1 = s2[k].nr1;
				y1 = s2[l].nr1;
				x2 = s2[k].nr2;
				y2 = s2[l].nr2;
				if ( x1 > y1 && x2 < y2 || x1 < y1 && x2 > y2 ){
					tak = 0;
					break;
				}
			}
			if (!tak)
				break;
		}
		if (tak)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	return 0;
}