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

#define MAXN 50003
#define MAXT 131075

const int M = 65536;

using namespace std;

struct wie{
	int lewy_x;
	int wys;
	int ind;
};
wie act;
wie tab1[MAXN];
wie tab2[MAXN];

int t,n,w;
int queryres;

bool zle;

int tree[MAXT];
int va,vb,v;

int x_1,x_2,y_1,y_2;
int gdzie_jest[MAXN];


int query(const int &pocz,const int &kon){
	va = pocz + M;
	vb = kon + M;
	
	if(pocz > kon)return 0;
	
	queryres = max(tree[va],tree[vb]);
	
	while((va/2) != (vb/2)){
		if(va % 2 == 0)queryres = max(queryres,tree[va+1]);
		if(vb % 2 == 1)queryres = max(queryres,tree[vb-1]);
		
		va/=2;
		vb/=2;
	}
	return queryres;
}
void insert(const int &gdzie, int ile){
	v = gdzie + M;
	tree[v] = ile;
	
	while(v != 1){
		v/=2;
		tree[v] = max(tree[v*2],tree[v*2+1]);
	}
}

bool cmp1(const wie &a,const wie &b){
	if(a.lewy_x < b.lewy_x)return 1;
	return 0;
}

int main(){
	scanf("%d",&t);
	for(int q=0;q<t;q++){
		scanf("%d",&n);
		scanf("%d",&w);
		for(int i=0;i<n;i++){
			scanf("%d %d %d %d",&x_1,&y_1,&x_2,&y_2);
			tab1[i].lewy_x = min(x_1,x_2);
			tab1[i].wys = abs((y_1-y_2));
			tab1[i].ind = i;
		}
		sort(tab1,tab1+n,cmp1);
		
		for(int i=0;i<n;i++){
			insert(i,tab1[i].wys);
			gdzie_jest[tab1[i].ind] = i;
			
	//		printf("tab1> na miejscu %d: ind:%d, wys:%d, lewy_x: %d\n",i,tab1[i].ind,tab1[i].wys,tab1[i].lewy_x);
		}
		
		for(int i=0;i<n;i++){
			scanf("%d %d %d %d",&x_1,&y_1,&x_2,&y_2);
			tab2[i].lewy_x = min(x_1,x_2);
			tab2[i].wys = abs((y_1-y_2));
			tab2[i].ind = i; 
		}
		sort(tab2,tab2+n,cmp1);
		
	//	for(int i=0;i<n;i++)printf("tab2> na miejscu %d: ind:%d, wys:%d, lewy_x: %d\n",i,tab2[i].ind,tab2[i].wys,tab2[i].lewy_x);
		
		zle = 0;
		
		for(int i=0;i<n;i++){
			//wez pierwszy wierzcholek z tablicy tab2
			act = tab2[i];
			
	//		printf("i:%d, act_wierzcholek: %d, w tab1 na miejscu: %d\n",i,act.ind,gdzie_jest[act.ind]); 
			
	//		printf("query: %d, act_wys: %d, w: %d\n",query(0,(gdzie_jest[act.ind]-1)),act.wys,w);
			
			if(( query(0,(gdzie_jest[act.ind]-1)) + act.wys) > w){
				zle = 1;
				break;
			} 
			insert(gdzie_jest[act.ind],0);
		}
		if(zle == 0)printf("TAK\n");
		else printf("NIE\n");
	}

return 0;
}