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
#define __STDC_FORMAT_MACROS
#include <inttypes.h>
#include <cstdio>
#include <queue>
#include <list>
#include <algorithm>

#define MIN(a,b) ((a) < (b)) ? (a) : (b)
#define MAX(a,b) ((a) > (b)) ? (a) : (b)

using namespace std;

struct Autko
{
	uint16_t i;
	uint32_t x, h;
};

bool operator<(Autko a, Autko b)
{
        return (a.x < b.x);
}

int main(void) {
        uint16_t t;
        scanf("%" SCNu16, &t);
        for (int i = 0; i < t; i++)
	{
		uint16_t n;
		uint32_t w;
		vector< Autko > v1, v2;
		v1.clear();
		v2.clear();
		list< Autko > l;
		l.clear();
		scanf("%" SCNu16 " %" SCNu32, &n, &w);
		for (int j = 0; j < n; j++)
		{
			uint32_t x1, y1, x2, y2;
			scanf("%" SCNu32 " %" SCNu32 " %" SCNu32 " %" SCNu32, &x1, &y1, &x2, &y2);
			Autko a;
			a.i = j;
			a.x = MIN(x1, x2);
			if (y1 < y2)
				a.h = y2 - y1;
			else
				a.h = y1 - y2;
			v1.push_back(a);
		}
		for (int j = 0; j < n; j++)
		{
			uint32_t x1, y1, x2, y2;
			scanf("%" SCNu32 " %" SCNu32 " %" SCNu32 " %" SCNu32, &x1, &y1, &x2, &y2);
			Autko a;
			a.i = j;
			a.x = MIN(x1, x2);
			if (y1 < y2)
				a.h = y2 - y1;
			else
				a.h = y1 - y2;
			v2.push_back(a);
		}
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		copy(v2.begin(), v2.end(), back_inserter(l));
		v2.clear();
		bool dasie = true;
		for (vector< Autko >::iterator j = v1.begin(); dasie && j != v1.end(); j++)
		{
			uint16_t k = j->i;
			uint32_t h = j->h;
			list< Autko >::iterator r = l.begin();
			for ( ; dasie && r->i != k; r++)
			{
				if (h + r->h > w)
					dasie = false;
			}
			l.erase(r);
		}
		printf("%s\n", dasie ? "TAK" : "NIE");
	}
        return 0;
}