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

using namespace std;

typedef long long ll;

struct dwa
{
	long long p,q,h;
	dwa() {}
	dwa(ll a, ll b, ll c) {p = a, q = b, h = c;}
};

bool comp(const dwa &A, const dwa &B)
{
	return A.p < B.p;
}

bool comp2(const dwa &A, const dwa &B)
{
	return A.q < B.q;
}

dwa T[50003];

int i0 = 1<<16;
struct tree
{
	ll v[1<<17];
	void ins(int p, ll k)
	{
		int i = p+i0;
		v[i] = k;
		i /= 2;
		while(i)
		{
			v[i] = max(v[2*i],v[2*i+1]);
			i /= 2;
		}
	}
	
	ll mx(int p)
	{
		int i = p+i0;
		ll m = 0;
		while(i > 1)
		{
			if (i%2 == 0) m = max(m,v[i+1]);
			i /= 2;
		}
		return m;
	}
	
	void clear()
	{
		memset(v,0,sizeof(v));
	}
};

tree Tr;

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		ll n,w;
		scanf("%lld%lld",&n,&w);
		for (int i = 0; i < n; i++)
		{
			ll x1,y1,x2,y2;
			scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
			T[i].h = abs(y1-y2);
			T[i].p = x1+x2;
		}
		for (int i = 0; i < n; i++)
		{
			ll x1,y1,x2,y2;
			scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
			T[i].q = x1+x2;
		}
		sort(T,T+n,comp2);
		for (int i = 0; i < n; i++) T[i].q = i;
		sort(T,T+n,comp);
		bool ok = true;
		for (int i = 0; i < n; i++)
		{
			Tr.ins(T[i].q,T[i].h);
			//for (int j = 0; j <= 10; j++) printf("%d ",Tr.v[j+i0/2]);
			//puts("");
			//printf("%d\n",Tr.mx(T[i].q));
			if (T[i].h+Tr.mx(T[i].q) > w) {ok = false; break;}
		}
		if (ok) puts("TAK");
		else puts("NIE");
		Tr.clear();
		memset(T,0,sizeof(T));
	}

	return 0;
}