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
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cstring>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define VI vector<int>
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lint long long int
#define max_n 50005

using namespace std;

int n,w;
int h[max_n];
int pos1[max_n];
int pos2[max_n];

vector<PII> dosortu;
VI merguj;
bool flaga;

void merge(int a,int b){
	int sr = (a+b)/2;
	VI res;
	int maxh = -1;
	int aktl,aktp;
	aktl = a; aktp = sr;
	while(aktl!=sr && aktp!=b){
		if(pos1[merguj[aktl]]<pos1[merguj[aktp]]){
			res.pb(merguj[aktl]);
			if(h[merguj[aktl]]+maxh>w) flaga = false; 
			aktl++;
		}
		else{
			res.pb(merguj[aktp]);
			maxh = max(maxh,h[merguj[aktp]]);
			aktp++;
		}
	}
	while(aktl!=sr){
			res.pb(merguj[aktl]);
			if(h[merguj[aktl]]+maxh>w) flaga = false; 
			aktl++;
	}
	while(aktp!=b){
			res.pb(merguj[aktp]);
			maxh = max(maxh,h[merguj[aktp]]);
			aktp++;
	}
	FOR(i,a,b){
		merguj[i] = res[i-a];
	}
}

void mergesort(int a,int b){
	if(!flaga) return ;
	int sr = (a+b)/2;
	if(b-a<2) return;
	mergesort(a,sr);
	mergesort(sr,b);
	merge(a,b);
}



int main(){
	int z; scanf("%d",&z);
	while(z--){
		dosortu.clear();
		merguj.clear();
		scanf("%d%d",&n,&w);
		FOR(i,0,n){
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			h[i] = max(b-d,d-b);
			pos1[i] = max(a,c);
		}
		FOR(i,0,n){
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			pos2[i] = max(a,c);
			dosortu.pb(mp(pos2[i],i));
		}
		sort(dosortu.begin(),dosortu.end());
		FOR(i,0,n) merguj.pb(dosortu[i].nd);
		flaga = true;	
		mergesort(0,n);

		if(flaga) printf("TAK\n");
		else printf("NIE\n");
	}
}