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

struct Car {
	int id;
	int size;
	int pos1;
	int pos2;
};

struct ComparePos1 {
public:
	bool operator()(const Car& c1, const Car& c2) {
		if (c1.pos1 == c2.pos1) {
			return (c1.size > c2.size);
		}
		return (c1.pos1 < c2.pos1);
	}
};

struct Place {
	int size;
	int position;

	bool operator<(const Place& other) const {
		return (position > other.position);
	}
};


bool solveProblem() {
	int n, w, x1, y1, x2, y2;
	vector<Car> cars;
	set<Place> places;

	scanf("%d %d", &n, &w);
	for(int i = 0; i < n; ++i) {
		Car c;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		c.id = i;
		c.size = (y1 < y2) ? (y2 - y1) : (y1 - y2);
		c.pos1 = (x1 < x2) ? x1 : x2;
		cars.push_back(c);
	}

	for (int i = 0; i < n; ++i) {
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		cars[i].pos2 = (x1 < x2) ? x1 : x2;
	}

	sort(cars.begin(), cars.end(), ComparePos1());

	Place newPlace;
	for (vector<Car>::iterator it = cars.begin(); it != cars.end(); ++it) {
		newPlace.size = it->size;
		newPlace.position = it->pos2;
		set<Place>::iterator next = places.lower_bound(newPlace);

		if (next != places.begin()) {
			set<Place>::iterator previous = next;
			--previous;
			if (previous->size + newPlace.size > w) {
				return false;
			} else if (previous->size >= newPlace.size) {
				continue;
			}
		}

		if (next == places.end() || next->size > newPlace.size) {
			places.insert(newPlace);
		} else {
			set<Place>::iterator current = next;
			while (next != places.end() && next->size <= newPlace.size) {
				++next;
			}
			places.erase(current, next);
			places.insert(newPlace);
		}
	}

	return true;
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		printf("%s\n", solveProblem() ? "TAK" : "NIE");
	}

	return 0;
}