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

struct Rectangle
{
	unsigned x, h, p;

	Rectangle(unsigned x1, unsigned y1, unsigned x2, unsigned y2, unsigned p): x(std::min(x1, x2)), h(std::max(y1, y2) - std::min(y1, y2)), p(p) {}

	bool operator<(const Rectangle &r) const
	{
		return x < r.x;
	}
};

bool can_do(unsigned n, unsigned w, const std::vector<Rectangle> &begin, const std::vector<Rectangle> &end)
{
	std::vector<unsigned> mapping(n);

	{
		std::vector<Rectangle>::const_iterator it;
		unsigned i;
		for(it = begin.cbegin(), i = 0; i < n; ++it, ++i)
			mapping[it->p] = i;
	}

	unsigned size = 1;
	while(size < n)
		size *= 2;

	std::vector<unsigned> tree(2 * size);

	for(unsigned i = 0; i < n; ++i)
		tree[size + i] = begin[i].h;

	for(unsigned i = size - 1; i != 0; --i)
		tree[i] = std::max(tree[2 * i], tree[2 * i + 1]);

	for(const Rectangle &r: end)
	{
		unsigned oldpos = mapping[r.p];
		unsigned max = 0;

		unsigned p = size;
		unsigned q = size + oldpos - 1;

		while(p < q)
		{
			if(p % 2 == 1)
				max = std::max(max, tree[p++]);
			if(q % 2 == 0)
				max = std::max(max, tree[q--]);
			p /= 2;
			q /= 2;
		}

		if(p == q)
			max = std::max(max, tree[p]);

		tree[size + oldpos] = 0;
		for(unsigned i = (size + oldpos) / 2; i != 0; i /= 2)
			tree[i] = std::max(tree[2 * i], tree[2 * i + 1]);

		if(max + r.h > w)
			return false;
	}

	return true;
}

int main()
{
	std::ios_base::sync_with_stdio(false);

	unsigned t;
	std::cin >> t;
	while(t--)
	{
		unsigned n, w;
		std::cin >> n >> w;

		std::vector<Rectangle> begin;
		std::vector<Rectangle> end;

		begin.reserve(n);
		for(unsigned i = 0; i < n; ++i)
		{
			unsigned x1, y1, x2, y2;
			std::cin >> x1 >> y1 >> x2 >> y2;
			begin.emplace_back(x1, y1, x2, y2, i);
		}

		end.reserve(n);
		for(unsigned i = 0; i < n; ++i)
		{
			unsigned x1, y1, x2, y2;
			std::cin >> x1 >> y1 >> x2 >> y2;
			end.emplace_back(x1, y1, x2, y2, i);
		}

		std::sort(begin.begin(), begin.end());
		std::sort(end.begin(), end.end());

		if(can_do(n, w, begin, end))
			std::cout << "TAK" << std::endl;
		else
			std::cout << "NIE" << std::endl;
	}

	return 0;
}