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
#include<bits/stdc++.h>
#define MAXN 65536
#define LL long long
#define PB push_back
using namespace std;

struct car
{
	LL d[4];
	LL pos;
};

bool cmp(car x, car y)
{
	return x.d[0] < y.d[0];
}

LL n, w, t;
bool global_flag = false;
vector<car> v, sec;
car q;
int wb[MAXN], tree[4*MAXN+2];

void add(int x, int val)
{
	x += MAXN;
	tree[x] = max(tree[x], val);
	x /= 2;
	while(x != 1)
	{
		tree[x] = max(tree[x*2], tree[x*2+1]);
		x /= 2;
	}
}

void remove(int x)
{
	x += MAXN;
	tree[x] = 0;
	x /= 2;
	while(x != 1)
	{
		tree[x] = max(tree[x*2], tree[x*2+1]);
		x /= 2;
	}
}

int query(int x, int y)
{
	if(x > y)return 0;
	int res = 0;
	x += MAXN;
	y += MAXN;
	res = max(tree[y], tree[x]);
	while(x/2 != y/2)
	{
		if(!(x&1))res = max(res, tree[x+1]);
		if((y&1))res = max(res, tree[y-1]);
		x /= 2;
		y /= 2;
	}
	return res;
}

void solve()
{
	v.clear(), sec.clear();
	memset(wb, 0, sizeof(wb));
	memset(tree, 0, sizeof(tree));
	cin >> n >> w;
	for(LL i = 0; i < n; i++)
	{
		q.pos = i;
		for(LL j = 0; j < 4; j++)
		{
			cin >> q.d[j];
		}
		if(q.d[3] < q.d[1])swap(q.d[3], q.d[1]);
		if(q.d[2] < q.d[0])swap(q.d[0], q.d[2]);
		v.PB(q);
	}
	for(LL i = 0; i < n; i++)
	{
		q.pos = i;
		for(LL j = 0; j < 4; j++)
		{
			cin >> q.d[j];
		}
		if(q.d[3] < q.d[1])swap(q.d[3], q.d[1]);
		if(q.d[2] < q.d[0])swap(q.d[0], q.d[2]);
		sec.PB(q);
	}
	sort(v.begin(), v.end(), cmp);
	sort(sec.begin(), sec.end(), cmp);
	for(int i = 0; i < n; i++)
	{
		add(i, v[i].d[3]-v[i].d[1]);
		wb[v[i].pos] = i;
	}
	for(int i = 0; i < n; i++)
	{
		int x = sec[i].d[3]-sec[i].d[1];
		if(x+query(0, wb[sec[i].pos]-1) > w)
		{
//			cout << x << ' ' << wb[sec[i].pos]-1 << endl;
			cout << "NIE\n";
			return;
		}
		remove(wb[sec[i].pos]);
	}
	cout << "TAK\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> t;
	while(t--)solve();
}