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

const int MX = 50005;

struct car
{
	int i, x, h;
	car() : i(0), x(0), h(0) {}
	car(int _i, int _x, int _h) : i(_i), x(_x), h(_h) {}
	void read(int _i)
	{
		i = _i;
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		x = min(x1,x2);
		h = abs(y2-y1);
	}
} c[MX], ck[MX];

bool operator<(const car &c1, const car &c2) { return c1.x < c2.x; }

int r[MX], p[MX];

int t[150000], M;

void init(int n)
{
	M = 1;
	while (M < n) M <<= 1;
	for (int i=0; i<(M<<1); i++) t[i] = 0;
}

void insert(int x, int a)
{
	int v = M+x;
	t[v] = a;
	while (v != 1)
	{
		v >>= 1;
		t[v] = max(t[v<<1], t[(v<<1)+1]);
	}
}

int query(int x1, int x2)
{
	int v1 = M+x1, v2 = M+x2;
	int a = max(t[v1], t[v2]);
	while ((v1>>1)!=(v2>>1))
	{
		if ((v1&1)==0) a = max(a, t[v1+1]);
		if ((v2&1)==1) a = max(a, t[v2-1]);
		v1 >>= 1;
		v2 >>= 1;
	}
	return a;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, w;
		scanf("%d%d", &n, &w);
		for (int i=0; i<n; i++) c[i].read(i);
		for (int i=0; i<n; i++) ck[i].read(i);
		sort(c, c+n);
		sort(ck, ck+n);
		for (int i=0; i<n; i++) r[c[i].i] = i;
		for (int i=0; i<n; i++) p[r[ck[i].i]] = i;
		//for (int i=0; i<n; i++) printf("%d ", p[i]);printf("\n");
		init(n);
		bool b = true;
		for (int i=0; i<n; i++)
		{
			//printf("query(%d, %d) = %d  >  %d-%d=%d\n", p[i], n-1, query(p[i], n-1), w,c[i].h,w-c[i].h);
			if (query(p[i], n-1) > w-c[i].h) { b = false; break; }
			//printf("insert(%d, %d)\n", p[i], c[i].h);
			insert(p[i], c[i].h);
		}
		printf(b ? "TAK\n" : "NIE\n");
	}
	return 0;
}