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
//Parking [B], PA 2014, runda 3
//Wiktoria Kośny
#include <cstdio>
#include <algorithm>
using namespace std;
const int MN=50009;
int n, wys, iprzyp, drzewo[3*MN], pot[30], ipot;
pair<pair<int, int>, int> dane[2][MN];

void wczytaj(){
	int a, i, x1, y1, x2, y2, d, v, h;
	scanf("%d %d", &n, &wys);
	for(d=0; d<2; d++){
		for(i=0; i<n; i++){
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			if(x2<x1)
				x1=x2;
			if(y2<y1){
				a=y2;
				y2=y1;
				y1=a;
			}
			h=y2-y1;
			dane[d][i]=make_pair(make_pair(x1, h), i);
		}
	}
	for(d=0; d<2; d++){
	sort(dane[d], dane[d]+n);
		for(i=0; i<n; i++){
			a=dane[d][i].second;
			dane[1-d][a].second=i;
		}
	}
}

void inic(){
	int i, j;
	ipot=1;
	pot[0]=1;
	while(pot[ipot-1]<n){
		pot[ipot]=pot[ipot-1]*2;
		ipot++;
	}
	pot[ipot]=pot[ipot-1]*2;
	for(i=0; i<=2*pot[ipot-1]; i++)
		drzewo[i]=0;
	for(i=0; i<n; i++)
		drzewo[i+pot[ipot-1]]=dane[1][i].first.second;
	for(j=ipot-2; j>=0; j--)
		for(i=pot[j]; i<pot[j+1]; i++)
			drzewo[i]=max(drzewo[2*i], drzewo[2*i+1]);
	
	

}

void akt(int v){
	if(v==0)
		return;
	drzewo[v]=max(drzewo[2*v], drzewo[2*v+1]);
	akt(v/2);
}

int maksimum(int sp, int sk, int v, int p, int k){
	//printf("maksimum %d %d %d %d %d\n", sp, sk, v, p, k);
	if(sk<p)
		return 0;
	if(sp>k)
		return 0;
	if(sp<=p && k<=sk)
		return drzewo[v];
	return max(maksimum(sp, sk, 2*v, p, (p+k)/2), maksimum(sp, sk, 2*v+1, (p+k)/2+1, k));
}

int main(){
	int a, i, j, x1, y1, x2, y2, d, v, h, czy;
	scanf("%d", &iprzyp);
	while(iprzyp>0){
		wczytaj();
		/*for(d=0; d<2; d++){
			for(i=0; i<n; i++)
				printf("%d %d %d\n", dane[d][i].first.first, dane[d][i].first.second, dane[d][i].second);
			printf("\n");
		}*/
		inic();
		
		/*for(j=ipot-1; j>=0; j--){
			for(i=pot[j]; i<pot[j+1]; i++)
				printf("%d ", drzewo[i]);
			printf("\n");
		}*/
		czy=1;
		for(i=0; i<n; i++){
			v=dane[0][i].second;
			//printf("zaraz %d %d %d %d %d\n", 0, v-1, 1, 0, pot[ipot-1]);
			a=maksimum(0, v-1, 1, 0, pot[ipot-1]-1);
			//printf("ide %d %d %d\n", i, v, a);
			if(dane[0][i].first.second+a>wys){
				czy=0;
				printf("NIE\n");
				//printf("%d %d %d %d %d\n", i, a, dane[0][i].first.second, a, wys);
				break;			
			}
			drzewo[v+pot[ipot-1]]=0;
			akt((v+pot[ipot-1])/2);
		}
		if(czy==1)
			printf("TAK\n");

		iprzyp--;
	}

	return 0;
}