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
116
#include <cstdio>
#include <algorithm>
#include <vector>
#define PB push_back
#define ST first
#define ND second
using namespace std;
typedef pair<int, int> PII;

const int MX = 50010;

vector<PII> v1, v2;
PII b[MX]; /* b to tablica pomocnicza dla procedury merge */
int pos[MX], h[MX], w, suf_max[MX];
bool res = true;

 
void merge(vector<PII> &a, PII *b, int p, int q, int r)
{
/* Procedura scalajaca dwa posortowane ciagi a[p..q] z a[q+1..r] przy *
* wykorzystaniu tablicy pomocniczej b, a konkretniej jej fragmentu   *
* b[p..r].                                                           */
	suf_max[q] = h[a[q].ST];
	for (int i = q - 1; i >= p; --i)
		suf_max[i] = max(suf_max[i+1], h[a[i].ST]);
	int i = p;
	int j = q + 1;
	int s = p;
	while (i <= q && j <= r)
	{
		if (pos[a[i].ST] < pos[a[j].ST])
		{
			b[s] = a[i];
			i++;
		}
		else
		{
			// Sprawdź czy da się zamienić miejscami
			if (suf_max[i] + h[a[j].ST] > w) res = false;
			b[s] = a[j];
			j++;
		}
		s++;
	}
	/* Skonczyl sie ktorys z ciagow: a[p..q] lub a[q+1..r]. Nalezy ogon *
	* drugiego ciagu przepisac do tablicy b na pozycje s+1..r.           */
	while (i <= q)
	{
		b[s] = a[i];
		i++;
		s++;
	}
	while (j <= r)
	{
		b[s] = a[j];
		j++;
		s++;	
	}
	/* Teraz pozostaje tylko przepisac wynik-posortowany ciag z tablicy  *
	* do tablicy a                                                      */
	for (int it = p; it <= r; it++)
		a[it] = b[it];
}

void mergesort(vector<PII> &a, PII *b, int p, int r)
{
	if (p == r) return;
	int q = (p + r)/2;
	mergesort(a, b, p, q);
	mergesort(a, b, q + 1, r);
	merge(a, b, p, q, r);
}

bool cmp (PII x, PII y)
{
	return x.ND < y.ND;
}

int main ()
{
	int t, n, x1, y1, x2, y2;
	
	scanf ("%d", &t);
	for (int j = 0; j < t; ++j)
	{
		v1.clear(); v2.clear(); res = true;
		scanf ("%d%d", &n, &w);
		for (int i = 0; i < n; ++i)
		{
			scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
			v1.PB(PII(i, max(x1, x2)));
			h[i] = abs(y1-y2);
		}
		for (int i = 0; i < n; ++i)
		{
			scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
			v2.PB(PII(i, max(x1, x2)));
		}
		sort(v1.begin(), v1.end(), cmp);
		sort(v2.begin(), v2.end(), cmp);
		for (int i = 0; i < n; ++i)
			pos[v2[i].ST] = i; // Pozycja auta v2[i].ST w nowym ciągu
			
		mergesort(v1, b, 0, n-1);
		/*for (int i = 0; i < n; ++i)
			printf ("%d ", v1[i].ST + 1);
		printf ("\n");
		for (int i = 0; i < n; ++i)
			printf ("%d ", v2[i].ST + 1);*/
			
		if (res)
			printf ("TAK\n");
		else 
			printf ("NIE\n");
	}
}