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
 97
 98
 99
100
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

#define MAX_N	50050

typedef vector<int> VI;

int t, n, w;
VI ax, aw, ah;
int ax1, ay1, ax2, ay2, n2;
VI ab, ae;

bool comp(const int l, const int r) {
        if (ax[l] != ax[r])
                return ax[l] < ax[r];

        return l < r;
}

int mw(int l, int r) {
	int ml, mr;

	++l; --r;
	ml = mr = 0;

	while (l < r) {
		ml = max(ml, ah[l]);
		mr = max(mr, ah[r]);
		l = l / 2 + l % 2;
		r = r / 2 + r % 2 - 1;
	}

	if (l == r) {
		ml = max(ml, ah[l]);
		mr = max(mr, ah[r]);
	}

	return max(ml, mr);
}

bool comp2(const int l, const int r) {
	if (aw[l] + aw[r] > w)
		return ax[l] == ax[r] ? l < r : ax[l] < ax[r];

	if (max(aw[l], aw[r]) + mw(l, r) > w)
		return ax[l] == ax[r] ? l < r : ax[l] < ax[r];

	return l < r;
}

void read(VI &at) {
	for (int i = 0; i < n; ++i) {
		scanf("%d %d %d %d", &ax1, &ay1, &ax2, &ay2);
		at[i] = i;
		ax[i] = ax1 < ax2 ? ax1 : ax2;
		aw[i] = ay1 < ay2 ? ay2 - ay1 : ay1 - ay2;
	}

	sort(at.begin(), at.end(), comp);

	for (int i = 0; i < n; ++i)
		ah[n2 + i] = aw[at[i]];
	for (int i = n2 - 1; i; --i)
		ah[i] = max(ah[2 * i], ah[2 * i + 1]);

	sort(at.begin(), at.end(), comp2);
}

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

	while (t--) {
		scanf("%d %d", &n, &w);

		ax.resize(n);	
		aw.resize(n);
		ab.resize(n);
		ae.resize(n);

		n2 = 1;
		while (n2 <= n)
			n2 *= 2;

		ah.resize(2 * n2);
	
		read(ab);
		read(ae);

		for (int i = 0; i < n; ++i)
			if (ab[i] != ae[i])
				w = 0;

		printf("%s\n", w ? "TAK" : "NIE");
	}

	return 0;
}