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

using namespace std;

int drz[1 << 21];
int n2;
void ustaw(int w, int x)
{
	w += n2;
	drz[w] = x;
	w /= 2;
	while(w)
	{
		drz[w] = max(drz[w * 2], drz[w * 2 + 1]);
		w /= 2;
	}
}

int odczyt(int w, int a, int b, int p, int k)
{
	if(b < p || k < a)
		return 0;
	if(a <= p && k <= b)
		return drz[w];
	return max(
		odczyt(w * 2, a, b, p, (p + k) / 2),
		odczyt(w * 2 + 1, a, b, (p + k) / 2 + 1, k)
	);
}

inline int odczyt(int a, int b)
{
	if(a > b)
		return 0;
	return odczyt(1, a, b, 0, n2 - 1);
}

int poz[1000005];
pair<pair<int, int>, int> v[2][1000005];

bool przyp()
{
	int n, height;
	scanf("%d%d", &n, &height);
	n2 = 1; while(n2 <= n) n2 *= 2;
	for(int i = n2 * 2 - 1; i >= 1; i--)
		drz[i] = 0;
	for(int j = 0; j < 2; j++)
	for(int i = 0; i < n; i++)
	{
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if(a > c)
			swap(a, c);
		if(b > d)
			swap(b, d);
		v[j][i] = make_pair(make_pair(a, d - b), i);
	}
	sort(v[0], v[0] + n);
	sort(v[1], v[1] + n);
	for(int i = 0; i < n; i++)
	{
		ustaw(i, v[0][i].first.second);
		poz[v[0][i].second] = i;
	}
	for(int i = 0; i < n; i++)
	{
		int g = odczyt(0, poz[v[1][i].second] - 1);
		if(g + v[1][i].first.second > height)
			return false;
		ustaw(poz[v[1][i].second], 0);
	}
	return true;
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
		printf(przyp() ? "TAK\n" : "NIE\n");
	return 0;
}