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

#define MP make_pair
#define ST first
#define ND second

using namespace std;

int testy, ilosc, bok, a1, b1, a2, b2, numer, odp;
bool res;
int Tree[500000];
int Zam[70000];
pair <pair<int,int>,pair<int,int> > Sam[70000];
pair <pair<int,int>,pair<int,int> > Pyt[70000];

const int INF = 1000000000;
const int czapa = 65536;

void PRZYGOTUJ();
void WYPELNIJ();
void ZNAJDZ_PRZEDZIAL(int,int,int,int,int);
void UAKTUALNIJ(int);

int main()
{
	scanf("%d", &testy);
	for(int i = 1; i <= testy; i++)
	{
		PRZYGOTUJ();
		scanf("%d %d", &ilosc, &bok);
		for(int j = 1; j <= ilosc; j++)
		{
			scanf("%d %d %d %d", &a1, &b1, &a2, &b2);
			Sam[j] = MP(MP(a1,a2),MP(abs(b1-b2),j));
		}
		sort(Sam+1,Sam+ilosc+1);
		for(int j = 1; j <= ilosc; j++)
		{
			numer = Sam[j].ND.ND;
			Tree[czapa+j] = bok - Sam[j].ND.ST;
			Zam[numer] = j;
		}
		WYPELNIJ();
		for(int j = 1; j <= ilosc; j++)
		{
			scanf("%d %d %d %d", &a1, &b1, &a2, &b2);
			Pyt[j] = MP(MP(a1,a2),MP(abs(b1-b2),Zam[j]));
		}
		sort(Pyt+1,Pyt+ilosc+1);
		for(int j = 1; j <= ilosc; j++)
		{
			numer = Pyt[j].ND.ND;
			odp = INF;
			ZNAJDZ_PRZEDZIAL(1,0,65535,0,numer-1);
			if(odp < Pyt[j].ND.ST)
				res = 0;
			else
				UAKTUALNIJ(numer+czapa);
		}
		if(res)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
}

void PRZYGOTUJ()
{
	for(int i = 0; i <= 200000; i++)
		Tree[i] = INF;
	res = true;
}

void WYPELNIJ()
{
	for(int i = 65535; i > 0; i--)
		Tree[i] = min(Tree[i*2],Tree[i*2+1]);
}

void ZNAJDZ_PRZEDZIAL(int v, int pocz, int kon, int szP, int szK)
{
	if(szP <= pocz && kon <= szK)
		odp = min(odp,Tree[v]);
	else
	{
		int sr = (pocz+kon)/2;
		if(sr >= szP)
			ZNAJDZ_PRZEDZIAL(v*2,pocz,sr,szP,szK);
		if(sr + 1 <= szK)
			ZNAJDZ_PRZEDZIAL(v*2+1,sr+1,kon,szP,szK);
	}
}

void UAKTUALNIJ(int v)
{
	Tree[v] = INF;
	v /= 2;
	while(v > 0)
	{
		Tree[v] = min(Tree[v*2],Tree[v*2+1]);
		v /= 2;
	}	
}