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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct samochod
{
	int x, y, wys, szer, nr;
	samochod(int a, int b, int c, int d, int e):x(min(a, c)), y(min(b,d)), wys(abs(d-b)),szer(abs(c-a)), nr(e) {}
};

bool operator< (samochod a, samochod b) {if (a.x!=b.x)return a.x<b.x; return a.y<b.y;}
void make_tree(int ile);
int tellmax(int p, int q, int skad, int dokad, int gdzie);
void setnull(int gdzie);
void update(int n);

vector<samochod> in;
vector<samochod> out;
int gdziewin[50009];
int tab[200009];
int pot;

int main()
{
	ios_base::sync_with_stdio(0);
	int ilez;
	cin>>ilez;
	for(int aa=0; aa<ilez; aa++)
	{
		int wys, ileaut;
		int tmpa, tmpb, tmpc, tmpd;
		cin>>ileaut>>wys;
		for(int n=0; n<ileaut; n++)
		{
			cin>>tmpa>>tmpb>>tmpc>>tmpd;
			in.push_back(samochod(tmpa, tmpb,tmpc, tmpd, n));
		}
		for(int n=0; n<ileaut; n++)
		{
			cin>>tmpa>>tmpb>>tmpc>>tmpd;
			out.push_back(samochod(tmpa, tmpb,tmpc, tmpd, n));
		}
		
		sort(in.begin(), in.end());
		sort(out.begin(), out.end());
		
		for(int n=0; n<ileaut; n++)
		{
			gdziewin[in[n].nr]=n;
//			gdziewout[out[n].nr]=n;
		}
		
		make_tree(ileaut);
		int dasie=1;
		for(int n=ileaut-1; n>=0; n--)
		{
			if(tellmax(gdziewin[out[n].nr]+1, ileaut-1, 0, pot-1, 1)+out[n].wys<=wys)
			{
				setnull(gdziewin[out[n].nr]);
			}
			else
			{
				dasie=0; break;
			}
		}
		
		if(dasie)
		{
			cout<<"TAK"<<endl;
		}
		else
		{
			cout<<"NIE"<<endl;
		}
		
		in.clear();
		out.clear();
	}
}
void make_tree(int ile)
{
	pot=1;
	while(pot<ile) pot*=2;
	for(int n=pot; n<=2*pot; n++) tab[n]=0;
	for(int n=0; n<ile; n++)
	{
		tab[pot+n]=in[n].wys;
	}
	for(int n=pot-1; n>0; n--)
	{
		tab[n]=max(tab[2*n],tab[2*n+1]);
	}
}
int tellmax(int p, int q, int skad, int dokad, int gdzie)
{
	if(p>q) return 0;
	if(p==skad && q==dokad) return tab[gdzie];
	if(p>(skad+dokad)/2) return tellmax(p, q, (skad+dokad)/2+1, dokad, gdzie*2+1);
	if(q<=(skad+dokad)/2) return tellmax(p, q, skad, (skad+dokad)/2, gdzie*2);
	return max(tellmax(p, (skad+dokad)/2, skad, (skad+dokad)/2, gdzie*2), tellmax((skad+dokad)/2+1, q, (skad+dokad)/2+1, dokad, gdzie*2+1));
}
void setnull(int gdzie)
{
	tab[gdzie+pot]=0;
	update((gdzie+pot)/2);			
}
void update(int n)
{
	tab[n]=max(tab[2*n], tab[2*n+1]);
	if(n>1) update(n/2);
}