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
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;

const int N=50006;

#define x first
#define y second
#define make(a,b) make_pair(a,b)

pair<int,int> sta[N];
pair<int,int> kon[N];
int H[N];

bool cmp(int a,int b)
{
	if (sta[a].x < sta[b].x) return 1;
	if (sta[a].x > sta[b].x) return 0;
	return sta[a].y < sta[b].y;
}

bool cmp1(int a,int b)
{
	if (kon[a].x < kon[b].x) return 1;
	if (kon[a].x > kon[b].x) return 0;
	return kon[a].y < kon[b].y;
}

int tab[N];
int meta[N];
int gdzie[N], n2;

int drz[(1<<17)+4];

void ustaw(int a, int x)
{
	a += n2;
	while(a)
	{
		if ( x > drz[a] ) drz[a]=x;
		else return;
		a/=2;
	}
}

int czytaj(int a)
{
	a += n2;
	int MAX = drz[a];
	if ( a==n2 ) return drz[1];
	while( a )
	{
		if ( a%2 == 0 ) MAX= max( MAX, drz[a+1] );
		a/=2;
	}
	return MAX;
}

int main()
{
	int t,n,a,b,c,d,w;
	bool mozna;
	scanf("%d",&t);
	while( t-- )
	{
		scanf("%d%d",&n,&w);
		n2=1;
		mozna = 1;
		while( n2<n ) n2*=2;
		for (int i=0;i<2*n2;i++) drz[i]=0;
		for (int i=0;i<n;i++)
		{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			sta[i].x = min(a,c);
			sta[i].y = min(b,d);
			H[i]=max(b,d) - sta[i].y;
			tab[i]=meta[i]=i;
		}
		for (int i=0;i<n;i++)
		{
			scanf("%d%d%d%d",&a, &b,&c,&d);
			kon[i].x = min(a,c);
			kon[i].y = min(b,d);
		}
		sort( tab, tab+n, cmp );
		sort( meta, meta+n, cmp1 );
		for (int i=0;i<n;i++) gdzie[ meta[i] ] = i;
/*		
		for (int i=0;i<n;i++) printf("%d ",tab[i] );
		printf("\n");
		for (int i=0;i<n;i++) printf("%d ",meta[i] );
		printf("\n");
*/
		for (int i=0;i<n;i++)
		{
			int h = czytaj( gdzie[ tab[i] ] );
			if ( h+ H[ tab[i] ] > w )
			{
				mozna = 0;
				break;
			}
			ustaw( gdzie[ tab[i] ], H[ tab[i] ] );
		}
		printf("%s\n", mozna? "TAK":"NIE");
	}
}