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

struct Pi
{
	int dx, dy, gx, gy, index;
	void in(int i)
	{
		scanf("%d%d%d%d", &dx, &dy, &gx, &gy);
		index = i;
	}
	void out()
	{
		printf("%d -- (%d,%d) , (%d,%d) ... h = %d\n", index, dx, dy, gx, gy,  gy - dy);
	}
	int h()
	{
		return gy - dy;
	}
};

bool cmp(Pi a, Pi b)
{
	return a.gx < b.gx;
}

const int MX = 50005, SMALL = 1e9, INF = 1e9;
Pi beg[MX], en[MX];
int q, gdzie[MX];

int main()
{
	scanf("%d", &q);

	while(q--)
	{
		int n, w;
		bool czy = true;
		scanf("%d%d", &n, &w);
	
		for(int i = 0; i < n; ++ i)
			beg[i].in(i);
		for(int i = 0; i < n; ++ i)	
			en[i].in(i);

		sort(beg, beg + n, cmp);
		sort(en, en + n, cmp);

		for(int i = 0; i < n; ++ i)
			gdzie[beg[i].index] = i;

		for(int i = 0; i < n; ++ i)
		{
			int co = gdzie[en[i].index];
			//printf("%d odpowiada %d w begu\n", i, co);
			for(int j = 0; j < co; ++ j)
				if(beg[co].h() + beg[j].h() > w)
					czy = false;
			beg[co].gy = -1 * SMALL;
			beg[co].gx = SMALL;
		}

		puts(czy ? "TAK" : "NIE");
	}

	return 0;
}