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
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

struct prostokat {
	long long int x1, y1;
	long long int x2, y2;
	int index;
};

bool comp(struct prostokat a, struct prostokat b) {
	return a.x1 < b.x1;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, w;
		scanf("%d%d", &n, &w);
		long long int aktX = 0;
		struct prostokat p1[n];
		struct prostokat p2[n];
		for (int i = 0; i < n; i++) {
			scanf("%lld%lld%lld%lld", &p1[i].x1, &p1[i].y1, &p1[i].x2, &p1[i].y2);
			p1[i].index = i;
		}
		for (int i = 0; i < n; i++) {
			scanf("%lld%lld%lld%lld", &p2[i].x1, &p2[i].y1, &p2[i].x2, &p2[i].y2);
			p2[i].index = i;
		}
		sort(p1, p1 + n, comp);
		sort(p2, p2 + n, comp);
		for (int i = 0; i < n; i++) {
			struct prostokat tmp = p1[i];
			p1[i].x1 = aktX;
			p1[i].x2 = aktX + (tmp.x2 - tmp.x1);
			p1[i].y1 = 0;
			p1[i].y2 = tmp.y2 - tmp.y1;
			aktX += (tmp.x2 - tmp.x1);
		}
		aktX = 0;
		for (int i = 0; i < n; i++) {
			struct prostokat tmp = p2[i];
			p2[i].x1 = aktX;
			p2[i].x2 = aktX + (tmp.x2 - tmp.x1);
			p2[i].y1 = 0;
			p2[i].y2 = tmp.y2 - tmp.y1;
			aktX += (tmp.x2 - tmp.x1);
		}
		int gdzie[n];
		for (int i = 0; i < n; i++) {
			gdzie[p1[i].index] = i;
		}
		bool prawda = true;
		for (int i = 0; i < n && prawda; i++) {
			int indOd = gdzie[p2[i].index];
			int indDo = i;
			if (indOd == indDo) continue;
			if (indOd < indDo) continue;
			for (int j = indOd; j > indDo && prawda; j--) {
				if (p1[j].y2 + p1[j - 1].y2 > w) {
					puts("NIE");
					prawda = false;
				}
				swap(p1[j], p1[j - 1]);
				gdzie[p1[j].index] = j;
				gdzie[p1[j - 1].index] = j - 1;
			}
		}
		if (prawda) puts("TAK");
	}
	return 0;
}