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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;

struct Car {
	int num;
	pair<int, int> pos;
};

struct MaxTree {
	int *el, s;
	MaxTree(int size) {
		el = new int[2 * (s = 1 << size)];
		for (int i = 0; i < 2 * s; i++) el[i] = 0;
	}

	~MaxTree() {
		delete[] el;
	}

	void Set(int p, int v) {
		for (p += s, el[p] = v, p >>= 1; p > 0; p >>= 1)
			el[p] = max(el[p << 1], el[(p << 1) + 1]);
	}

	int Find(int p, int k) {
		int m = -1;
		p += s;
		k += s;

		while (p < k) {
			if ((p & 1) == 1) m = max(m, el[p++]);
			if ((k & 1) == 0) m = max(m, el[k--]);
			p >>= 1;
			k >>= 1;
		}

		if (p == k) m = max(m, el[p]);
		return m;
	}
};

const int MAX_N = 50000;
int t, w, n;
int h[MAX_N], p[MAX_N];
struct Car iset[MAX_N], fset[MAX_N];


int get_tree_size(int n)
{
	int k = 0;
	int nk = 1;
	while (nk < n) {
		k++;
		nk *= 2;
	}
	return k;
}

pair<int,int> ld_corner(int x1, int y1, int x2, int y2)
{
	return make_pair(min(x1,x2), min(y1,y2));
}

bool car_sort(const struct Car& lhs, const struct Car& rhs)
{
	return lhs.pos < rhs.pos;
}

void print_seq(struct Car* seq)
{
	for (int i = 0; i < n; i++) {
		printf("%d: (%d, %d)\n", seq[i].num, seq[i].pos.first, seq[i].pos.second);
	}
}

bool solve()
{
	int x1, y1, x2, y2;

	scanf("%d%d", &n, &w);

	// Initial positions
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		h[i] = abs(y2 - y1);
		iset[i].num = i;
		iset[i].pos = ld_corner(x1, y1, x2, y2);
	}

	// Final positions
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		fset[i].num = i;
		fset[i].pos = ld_corner(x1, y1, x2, y2);
	}

	sort(iset, iset + n, car_sort);
	sort(fset, fset + n, car_sort);

	MaxTree tree(get_tree_size(n));	
	for (int i = 0; i < n; i++) {
		// Tell me where am I (inverse permutation)
		p[iset[i].num] = i;
		// Init tree
		tree.Set(i, h[iset[i].num]);
	}

	for (int i = 0; i < n; i++) {
		int idx = p[fset[i].num];
		int m = (idx > 0 ? tree.Find(0, idx - 1) : 0);
		if (m + h[fset[i].num] > w)
			return false;
		tree.Set(idx, 0);		
	}


	
	return true;
}

int main()
{
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
		printf(solve() ? "TAK\n" : "NIE\n");

	return 0;
}