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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define VAR(i,n) __typeof(n) i=(n)
#define FOREACH(i,n) for(VAR(i,(n).begin());i!=(n).end();i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define SIZE(n) (int)(n).size()
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
const int M1=50003,INF=2000000002;
struct samo
{
	int h,nr,x,poz;
};
bool operator<(samo a,samo b)
{
	return a.x<b.x;
}
bool cz_wspolna(pair<int,int>p1,pair<int,int>p2)
{
	if (!(p2.ND>p1.ST))swap(p1,p2);
	return p1.ND>=p2.ST;
}
inline int l_syn(const int &in)
{
	return (in*2)+1;
}
inline int p_syn(const int &in)
{
	return (in*2)+2;
}
inline int ojc(const int &in)
{
	return (in-1)/2;
}
int t,n,w,odp[M1];
int n2,n3;
struct drzewo
{
	int tree[M1*2];
	void clear()
	{
		n2=1;
		while(n2<n)n2*=2;
		n3=n2*2-1;
		REP(i,n3)
			tree[i]=0;
	}
	int maxx(const int &w,pair<int,int>prz,const pair<int,int>&prz_doc)
	{
		if (!(cz_wspolna(prz,prz_doc)))return -INF;	
		if (prz.ST>=prz_doc.ST && prz.ND<=prz_doc.ND)
			return tree[w];
		int mid=(prz.ST+prz.ND)/2;
		return max(maxx(l_syn(w),MP(prz.ST,mid),prz_doc),
			maxx(p_syn(w),MP(mid+1,prz.ND),prz_doc));
	}
	void plusik(int w,const int &co)
	{
		w+=n2-1;
		tree[w]+=co;
		while(w!=0)
		{
			w=ojc(w);
			tree[w]=max(tree[l_syn(w)],tree[p_syn(w)]);
		}
	}
};
samo sam[2][M1];
//numer pozycja
drzewo d;
void main2()
{
	cin>>t;
	REP(i5,t)
	{
		cin>>n>>w;
		d.clear();

		REP(i2,2)
			REP(i,n)
			{
				int y1,y2,a;
				cin>>sam[i2][i].x>>y1>>a>>y2;
				sam[i2][i].h=y2-y1;
				sam[i2][i].nr=i;
			}
		if (n==1)
		{
			cout<<"TAK"<<endl;
			continue;
		}
		REP(i2,2)sort(sam[i2],sam[i2]+n);
		REP(i,n)
			odp[sam[1][i].nr]=i;
		REP(i,n)sam[0][i].poz=odp[sam[0][i].nr];
		REP(i,n)
		{
			int maxi=d.maxx(0,MP(0,n2-1),MP(sam[0][i].poz+1,n2-1));
			if (maxi+sam[0][i].h>w)
				goto kon;
			d.plusik(sam[0][i].poz,sam[0][i].h);
		}
		cout<<"TAK"<<endl;
		continue;
kon:;
		cout<<"NIE"<<endl;
		continue;
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	main2();
}