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

#define ST first
#define ND second

using namespace std;

int tree[131080];
const int tree_base = 65536;

int z, n, w;
pair<pair<int, int>, pair< pair<int, int>, int > > before[50010], after[50010];
int idx_before[50010];
bool noWay;

void make_tree()
{
	for(int i = tree_base - 1; i >= 1; i--)
		tree[i] = max(tree[i<<1], tree[(i<<1) + 1]);
}

int height(int bottom, int top)
{
	int res = top - bottom;
	if(res < 0)
		res = -res;
	
	return res;
}

int get_max(int begin)
{
	begin += tree_base;
	int end = (tree_base<<1) - 1;
	int result = 0;
	
	while(begin < end)
	{
		if(begin % 2 == 1)
			result = max(result, tree[begin++]);
		if(end % 2 == 0)
			result = max(result, tree[end--]);
		begin >>= 1;
		end >>=1;
	}
	if(begin == end)
		result = max(result, tree[begin]);
	
	return result;
}

void update(int pos, int val)
{
	pos += tree_base;
	tree[pos] = val;
	
	while(pos > 1)
	{
		pos >>= 1;
		tree[pos] = max(tree[pos<<1], tree[(pos<<1) + 1]);
	}
}
	
int main()
{
	scanf("%d", &z);
	while(z--)
	{
		noWay = false;
		scanf("%d%d", &n, &w);
		for(int i = 0; i < n; i++)
		{
			scanf("%d%d%d%d", &before[i].ST.ST, &before[i].ST.ND, &before[i].ND.ST.ST, &before[i].ND.ST.ND);
			before[i].ND.ND = i + 1;
		}
		for(int i = 0; i < n; i++)
		{
			scanf("%d%d%d%d", &after[i].ST.ST, &after[i].ST.ND, &after[i].ND.ST.ST, &after[i].ND.ST.ND);
			after[i].ND.ND = i + 1;
		}
		sort(before, before+n);
		sort(after, after+n);
		
		for(int i = 0; i < n; i++)
		{
			idx_before[before[i].ND.ND] = i;
		}
		
		for(int i = 0; i < n; i++)
			tree[tree_base + i] = height(before[i].ST.ND, before[i].ND.ST.ND);
		for(int i = tree_base + n; i < tree_base<<1; i++)
			tree[i] = 0;
			
		make_tree();
		
		for(int i = n-1; i >= 0; i--)
		{
			if(w - get_max(idx_before[after[i].ND.ND]+1) < height(after[i].ST.ND, after[i].ND.ST.ND))
			{
				noWay = true;
				break;
			}
			else
				update(idx_before[after[i].ND.ND], 0);
		}
		
		if(noWay == false)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	
	return 0;
}